체스판 다시 칠하기

문제: 체스판 다시 칠하기 (백준 1018번)

구조 분석

처음 문제를 봤을 때, 이를 수학적으로만 풀려고 해서 어려웠다. 그러나 이러한 문제는 convolution 계산하듯이 8*8의 체스보드 프레임을 입력받은 이차원배열 위로 움직이면서 해당 8*8 보드 프레임 위에서의 다시 칠해야 하는 정사각형의 수를 구한 뒤, 모든 경우에서의 최솟값을 구하는 방식으로 풀어야 한다. 이러한 방식은 전형적인 brute force 방식을 따른다.

풀이 방법

이중 for문 위에서 8*8 보드 프레입을 움직이고 이 안에서 다시 이중 for문을 이용해서 다시 칠해야 하는 정사각형의 수를 구한다. 이때, BW로 시작하는 경우와 WB로 시작하는 경우 모두 구한 뒤, 둘 중 최솟값을 채택하는 방식으로 풀어야 한다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#define MIN(a,b) (a<b?a:b)
using namespace std;

int B[50][50];

int main() {
    int n, m;
    cin >> n >> m;
    string str;
    for (int i=0; i<n; i++) {
        cin >> str;
        for (int j=0; j<m; j++) {
            if (str[j]=='B') B[i][j] = 0;
            else if (str[j]=='W') B[i][j] = 1;
        }
    }
    int min = n*m;
    int cnt1;
    int cnt2;
    for (int I=0; I<n-7; I++) {
        for (int J=0; J<m-7; J++) {
            cnt1 = 0;
            cnt2 = 0;
            for (int i=I; i<I+8; i++) {
                for (int j=J; j<J+8; j++) {
                    if ((i+j)%2==0 && B[i][j]==0) cnt1++;
                    else if ((i+j)%2==1 && B[i][j]==1) cnt1++;
                    else if ((i+j)%2==0 && B[i][j]==1) cnt2++;
                    else if ((i+j)%2==1 && B[i][j]==0) cnt2++;
                }
            }
            min = MIN(min,cnt1);
            min = MIN(min,cnt2);
        }
    }
    cout << min << "\n";
    return 0;
}  

정리

이는 4중 for문을 이용하므로 각 반복문에서의 iterator를 헷갈리지 않고 잘 써야 한다. 나의 경우 iterator가 잘못된 줄 모르고 다른 부분에서 수정하느라고 삽질을 많이했다. 또한 연속되는 문자열을 입력받는 방법으로는 아래의 두 가지 방법을 사용할 수 있다.

1. string 이용하기

   B[50][50];
   string str;  
   int n,m;
   for (int i=0; i<n; i++) {
    cin >> str;
    for (int j=0; j<m; j++) {
        if (str[j] == 'B') B[i][j] = 0;
        else B[i][j] = 1;
    }
   }  
   

2. char 이용하기

   B[50][50];
   char c;
   int n,m;
   for (int i=0; i<n; i++) {
    for (int j=0; j<m; j++) {
        cin >> c;
        if (c == 'B') B[i][j] = 0;
        else B[i][j] = 1;
    }
   }  
   

   이와 같은 방법을 이용해서 입력받는 부분에서부터 헤매지 말자.