[백준] 1018번 체스판 다시 칠하기 (C++) - brute force

문제

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

코드

#include <iostream>
#include <string>

using namespace std;

int main(){
  int n, m, count, minValue = 32;
  char board[50][50] = {};
  cin >> n >> m;

  for(int i=0; i<n; i++){
    string s;
    cin >> s;
    for(int j=0; j<m; j++){
      board[i][j] = s[j];
    }
  }

  for(int i=0; i<n-7; i++){
    for(int j=0; j<m-7; j++){
      count = 0;
      for(int a=i; a<i+8; a++){
        for(int b=j; b<j+8; b++){
          if(((a+b)%2 == 0 && board[a][b] == 'B') || (a+b)%2 != 0 && board[a][b] == 'W'){
            count += 1;
          } 
        }
      }
      if(minValue > min(count, 64-count)){
        minValue = min(count, 64-count);
      }
    }
  }
  cout << minValue;
  
  return 0;
}

정리

brute force 문제

brute force란? 가능한 모든 경우의 수를 탐색하여 요구조건에 충족되는 결과만을 가져오는 알고리즘이다. 이 알고리즘의 장점은 예외없이 확실한 정답을 도출한다. 그러나 시간이 오래 걸릴 수 있다는 단점이 있다.

 

위 문제도 4중 for문을 사용해 모든 경우의 수를 탐색하여 정답을 도출했다.

 

+ 붙어서 주어지는 2차원 배열 입력받는 방법

cin >> n >> m;

for(int i=0; i<n; i++){
    string s;
    cin >> s;
    for(int j=0; j<m; j++){
      array[i][j] = s[j];
    }
  }

참조

https://hcr3066.tistory.com/26

https://foxtrotin.tistory.com/445