[백준] 1018 체스판 다시 칠하기

Posted on | In

간만에 브루트포스 문제를 가져 왔다! 처음부터 찬찬히 공부하려고 브루트포스 문제를 풀어보기 시작했는데 옛날에는 참 어려웠던 문제들인데두 지금 보니 나름 괜찮은 것 같기도 하고… 이 문제도 작년 여름에? 처음 풀어 봤던 문제인데 그때는 어려웠었다. 와 이걸 나 혼자 어떻게 풀지…? 이런 생각을 하면서 풀었었는데 지금 와서 보니까 그렇게 오래 걸리는 풀이도 아니고 그냥 어찌저찌 풀만 한 문제가 된 것 같다. 신기하다 암것도 안 한거 같은데 늘긴 늘었나부다..!

문제 설명

문제 링크 : 링크

이 문제는 검흰 검흰 이런 식으로 우리가 늘 생각하는 그런 체스판이 아니라 중간중간 잘못 칠해진 네모가 있는 체스판이다. 우리는 어차피 8x8 체스판만 사용하기 때문에 이 잘못 칠해진 체스판이 8x8보다 크더라도(가로던 세로던 둘다던) 상관이 없고 그걸 적당히 잘 8x8 크기가 되게 가장자리 부분을 떼 버리면 된다. 여기서 문제는 이 가장자리 부분을 어떻게 뗄 때 우리가 이 잘못 칠해진 체스판에서 다시 칠해야 할 정사각형이 가장 작은가를 묻는 문제이다. 따라서 내가 만약 10x10의 잘못 칠해진 체스판을 가지고 있다면 여기서 내가 맨 위 두줄 그리고 맨 오른쪽 두줄을 떼서 8x8을 만들 수도 있는 거고 위 아래 각각 한줄 왼 오 각각 한줄을 떼서 8x8을 만들 수도 있는 거다. 여기서 다시 칠해야 할 정사각형이 가장 작게 되도록만 만들어 주면 된다.

문제 풀이

이 문제는 브루트포스 문제이므로, 설마 이걸 노가다로 다 체크하는거야? 라고 생각할 수 있지만 그 풀이가 맞다. 나는 4중 포문이 나왔다. 보통 4중 포문을 써서 잘 푸는 것 같다. 그래서 내가 너무 이상하게 풀었나? 라는 걱정을 하지 않아도 된다. 그럼 이제 진짜 풀이를 설명하겠다.

1. 가장 왼쪽 포인트 잡기

내가 만약 10x10의 체스판을 가지고 있을 때, 내가 (0,0)을 가장 왼쪽 포인트로 잡을 수도 있고(이렇게 되면 맨 오른쪽 두줄과 맨 아랫쪽 두줄이 떼져서 8x8을 만든다고 생각하면 된다) 아니면 (0,1)… (1,0)…(1,1) 등등을 내가 다듬은 (8x8) 체스판의 가장 왼쪽 포인트로 잡을 수 있다. 그리고 이 왼쪽 포인트로 가능한 부분은 세로로 봤을 때도 8줄이 남아 있어야 하고 가로로 봤을 때도 8줄이 남아 있어야 한다. 이게 무슨 말이냐면, 10x10에서 내가 (8,8)을 가장 왼쪽 포인트로 잡으면 체스판이 8x8 형태가 나올 수가 없게 된다. (더 작아진다) 따라서 8x8 형태를 유지해줄 수 있는 최소한의 예의를 지키면서 왼쪽 포인트를 설정해주어야 한다. 이것 때문에 sx, sy의 범위는 n-8, m-8이 된다. 만약 sx가 n-8보다 커지면 (sx, sy)가 가장 왼쪽 포인트인 다듬어진 체스판은 절대 8의 가로를 가질 수가 없다. 그 전에 체스판이 끝난다. 이런 식으로 가장 왼쪽 포인트를 설정해주면 8x8 체스판이므로 체스판이 하나가 결정이 된다. 결국, 특정한 한 경우를 고려할 수 있게 된다는 말이다.

2. 다시 칠해야 되는 정사각형 세기

자 위에서 가장 왼쪽 포인트를 잡아서 8x8의 무수한 체스판들 중 한 경우를 고려할 수 있게 되었다. 이렇게 되면 우리는 그냥 잘못 칠해진 정사각형만 세면 된다. 여기서 주목해야 하는 점은, 체스판의 x좌표 y좌표를 더했을 때 검은색 정사각형끼리 2로 나눈 나머지가 같고, 하얀색 정사각형끼리 2로 나눈 나머지가 같다는 점이다. 따라서 (x+y)%2가 같은 (x,y)끼리는 같은 색깔을 공유해야 한다. 이걸 베이스로 이중 포문을 또 만들 수 있다. 또한, 문제에서도 말했듯이, 체스판은 가장 왼쪽 포인트가 W인 경우와 B인 경우 딱 두 가지 경우밖에 존재하지 않는다. 따라서 이 두 경우에 대해서만 다시 칠해야 하는 정사각형을 세 주면 이 특정한 왼쪽 포인트에서 다시 칠해야 하는 정사각형 개수를 셀 수 있다. 나는 이때 가장 왼쪽 포인트가 무조건 W라고 생각하고 다시 칠해야 하는 정사각형을 셌다. 왜 이렇게 했냐면, 만약 가장 왼쪽 포인트가 무조건 B인 경우가 최소인 경우가 된다면 그 경우는 내가 아까 센 W라고 생각했을 때랑 왼전 정반대로 칠해주면 된다. 왼쪽 포인트가 B였던 경우, W라고 생각하고 다시 칠해야 했던 정사각형은 맞아서 다시 칠할 필요가 없는 정사각형이 되고 맞아서 넘어갔던 정사각형들은 다시 칠해야 하는 정사각형이 된다. 결국 맞았던 애들은 틀리게 되고 틀렸던 애들은 맞게 된다. 지금 8x8 체스판이므로 총 64개의 정사각형이 있고, 내가 만약 왼쪽 포인트가 W일 때 다시 칠해야 하는 정사각형이 K개라고 했다면 왼쪽 포인트가 B일때 다시 칠해하 하는 정사각형은 64-k가 되는 것이다. 우리는 두 경우(왼쪽 포인트가 W or B) 중 최소인 경우를 골라야 하므로 둘 중 더 작은 경우를 최소로 채택하면 된다. 이것을 1번의 가장 왼쪽 포인트에 대해서 반복해 주면 최소 값을 구할 수 있다! 이렇게 하면 잘 설명했는지는 모르겠지만 그렇게 복잡하지 않게 풀 수 있는 문제가 된다.

코드를 첨부하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>

int main(){
    int n, m;
    char b[51][51];
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++){
        scanf("%s", b[i]);
    }

    int min=10000000;
    for(int sx=0;sx<=n-8;sx++){
        for(int sy=0;sy<=m-8;sy++){
            int wrong=0;
            for(int i=sx;i<sx+8;i++){
                for(int j=sy;j<sy+8;j++){
                    if((i+j)%2==0 && b[i][j]=='B') wrong++;
                    else if((i+j)%2==1 && b[i][j]=='W') wrong++;
                }
            }
            wrong=(wrong<64-wrong)?wrong:64-wrong;
            if(wrong<min) min=wrong;
        }
    }
    printf("%d\n", min);

}