[BOJ - 1018] 체스판 다시 칠하기

💡문제 한마디

이게 맞나하는 코드가 나오는 브루트포스 알고리즘...

문제 링크

체스판 다시 칠하기

코드

#include <iostream>
#include <vector>

using namespace std;



int main(void){
  int N, M;
  int min = 32;
  char color[3]= {'W','B'};
  int Check;
  int tem;
  cin >> N >> M;
  vector <vector<char>> v(N,vector<char>(M));

  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin >> v[i][j];
    }
  }

  for(int startRow=0;startRow<=N-8;startRow++){
    for(int startCol=0;startCol<=M-8;startCol++){

      Check= (v[startRow][startCol] == color[0] ? 1 : 0);
      tem =0;
      for(int i=startRow;i<startRow+8;i++){
        Check = !Check;
        for(int j=startCol;j<startCol+8;j++){
          if(v[i][j] != color[Check]){
            tem++;
          }
          Check = !Check;
        }
      }

      if(tem>32){
        tem=64-tem;
      }
      if(min>tem){
        min =tem;
      }
    }
  }

  cout << min;
}

풀이

for(int startRow=0;startRow<=N-8;startRow++){
    for(int startCol=0;startCol<=M-8;startCol++){

      Check= (v[startRow][startCol] == color[0] ? 1 : 0);
      tem =0;
      for(int i=startRow;i<startRow+8;i++){
        Check = !Check;
        for(int j=startCol;j<startCol+8;j++){
          if(v[i][j] != color[Check]){
            tem++;
          }
          Check = !Check;
        }
      }

      if(tem>32){
        tem=64-tem;
      }
      if(min>tem){
        min =tem;
      }
    }
  }

• 항상 8 * 8로 묶여 있어야 하므로 시작점의 범위는 N-8, M-8 로 정할 수 있음.
• Check라는 변수를 두어서 매번 W,B가 번갈아 나와야 하므로 그걸 검사 도와주게 함.
• 그리고 줄이 바뀌면 한번 더 바뀌어야 하므로 한번 바꿔줌. (Check 시작이 반대로 된 이유는 단지 for문 처음에 Check를 바꾸기 때문임)
• 최솟값 갱신을 그때 그때 해주되, 32가 넘으면 반대 케이스가 더 작은 거니까 64-tem을 해줌.

배운 점

브루트포스 알고리즘의 실행시간을 줄일 수 있는 방법은 조건(시작, 끝, 변환하는 값)을 잘 찾아보는 것!