[C언어] 백준 1018. 체스판 다시 칠하기

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

구상

 

표 형태이니 2차원 배열로 선언해준다. 표 크기의 최댓값이 50x50인데, 배열에는 null값을 저장할 칸이 하나 더 필요해서 가로는 51칸으로 설정한다.

char arr[50][51];

 

체스판을 8x8 사이즈로 자를 수 있는 경우의 수를 따지고, 각각의 케이스 안에서 체스판을 다시 칠하는 경우를 생각한다.

 

13x10짜리 보드가 있다고 가정하자. 이 보드를 8x8 크기의 틀로 잘라낸다. 왼쪽 위에서부터 한 칸씩 훑으면서 자른다.

체스판의 가장 왼쪽 위인 첫 번째 칸을 (0,0)이라는 좌표로 생각해보자. 오른쪽 칸은 (0,1)이 되고, 아래 칸은 (1,0)이 된다.

 

8x8짜리 틀은 (0,0)~(7,7)구역을 자른다.

다음으로는 (0,1)~(7,8),

(0,2)~(7,9) 구역을 자르게 되고, 여기까지 자르고 나면 아래칸으로 이동해 (1,0)~(8,7) 구역을 자른다.

계속 이동해서 마지막에 (2, 5)에서 (9,12) 구역을 자른다.

틀의 가장 왼쪽 위에 오는 칸은 가장 오른쪽 아래에 오는 칸에 비해 x축으로 -7, y축으로 -7에 위치해 있다.

입력받은 세로 길이를 a, 가로 길이를 b라고 하면

틀은 초기 위치(0,0)에 비해 x축으로 a-8, y축으로 b-8만큼 이동해야 한다.

 

왜 위의 경우는 7만큼 이동하고 밑의 경우는 8만큼 이동하냐면, 좌표가 (1,1)이 아닌 (0,0)부터 시작하기 때문이다.

가로로 10칸이면 가장 끝에 있는 칸의 x 좌표는 9가 된다. 배열의 인덱스가 0부터 시작하니 (0,0)으로 설정했다.

 

틀이 이동하는 모든 경우에 대해 생각해야 하므로, 이를 반복문으로 만든다.

for (int x = 0; x < a - 7; x++) {   //x좌표와
        for (int y = 0; y < b - 7; y++) {   //y좌표가 도착점에 갈 때까지 반복
        
        }
}

 

이제 체스판을 어떻게 칠해야 하는지 생각해보자.

체스판은 첫째 칸이 W인 경우와 B인 경우, 두 가지밖에 없다. 

또한 번갈아가면서 칠해져야 하고, 색이 두 가지이니 칸을 홀수칸과 짝수칸으로 나누어 생각해볼 만하다.

 

시작 좌표가 (0,0)이었으니까, 0을 짝수라 생각하면 체스판은 위와 같이 구성되어야 한다. 

(짝,짝)-(홀,홀) / (짝,홀)-(홀,짝)끼리 같은 색이어야 한다.

잘 생각해보면, 짝수 + 짝수 = 짝수, 홀수 + 홀수 = 짝수, 짝수 + 홀수 = 홀수이다.

x좌표와 y좌표를 합했을 때 짝수인 경우와 홀수인 경우, 두 가지로 압축해서 생각할 수 있다.

 

그런데 틀이 보드의 가장 왼쪽 위에 있을 때는 문제가 없지만, 틀이 이동하면 문제가 생긴다.

우리는 틀이 (0,0)에서 출발한다는 가정 하에 위의 표를 만들었다. 틀이 이동해서 (0,1)부터 시작하게 되면 원점이 달라져서 또 다른 경우가 된다.

 

그래서, 원점을 틀이 이동한 위치로 다시 설정해줘야 한다.

 

for (int i = x; i < x + 8; i++) {
                for (int j = y; j < y + 8; j++) {
                    //합이 짝수일 때
                    if (((i - x + j - y) % 2) == 0) {
                        //해당하는 좌표가 W가 아니면
                        if (arr[i][j] != 'W')
                            temp1++;    //다시 칠하기
                    }
                    //합이 홀수일 때
                    else {
                        //해당하는 좌표가 B가 아니면
                        if (arr[i][j] != 'B')
                            temp1++;    //다시 칠하기
                    }
                }
            }

 

틀이 8x8이니 64번 반복해서 색을 검증하고, 문제가 있으면 다시 칠해야 한다. 

틀은 계속 이동하니까 이동하는 x좌표와 y좌표를 초기값으로 설정해주고 반복문을 돌려야 한다.

틀이 (1,3)에서 시작한다면 이를 (0,0), 즉 (짝,짝)이라 가정하고 색을 검사해야 한다.

그러려면 시작 위치의 값을 가지고 있는 x와 y를 각 축에 대해서 빼주면 된다. 빼주고 난 다음, 합이 짝수일 때와 홀수일 때를 생각해서 색이 다르다면 임시 변수를 증가시킨다.

 

첫째 칸을 하얀색인 경우와 검은색인 경우로 나누어 반복문을 두 번 만들면 된다.

 

한 가지 더 생각해야 하는 점은, 

WWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

이런 보드가 있다고 하면 첫째 칸이 W이지만 첫째 칸을 B로 바꾸는 경우가 색을 최소로 다시 칠하는 방법이다. 

그래서 W인 경우와 B인 경우를 나눠서 if문으로 구분해버리면 위와 같은 경우에 첫째 칸이 W이니 다른 모든 칸을 바꿔버리는 불상사가 발생한다. 

 

이런 경우를 대비해 if문으로 나누지 않고 첫째 칸을 W로 다시 칠해보는 방법과 B로 다시 칠해보는 방법을 모두 실행하고, 각각의 경우에 다시 칠한 횟수를 비교하고 더 작은 값을 결과에 저장한다.

코드

#include <stdio.h>

int main(void)
{
    char arr[50][51];
    int a, b, count = 3000; //count는 초기에 아주 큰 값으로 초기화
    scanf("%d%d", &a, &b);
    for (int i = 0; i < a; i++)
        scanf("%s", arr[i]);

    int temp1 = 0, temp2 = 0;   //첫째 칸을 W로 할 때, B로 할 때 따로 계산하기 위함
    for (int x = 0; x < a - 7; x++) {   //x좌표와
        for (int y = 0; y < b - 7; y++) {   //y좌표가 도착점에 갈 때까지 반복
            //첫째 칸을 W로 만드는 경우
            for (int i = x; i < x + 8; i++) {
                for (int j = y; j < y + 8; j++) {
                    //합이 짝수일 때
                    if (((i - x + j - y) % 2) == 0) {
                        //해당하는 좌표가 W가 아니면
                        if (arr[i][j] != 'W')
                            temp1++;    //다시 칠하기
                    }
                    //합이 홀수일 때
                    else {
                        //해당하는 좌표가 B가 아니면
                        if (arr[i][j] != 'B')
                            temp1++;    //다시 칠하기
                    }
                }
            }
            //첫째 칸을 B로 만드는 경우
            for (int i = x; i < x + 8; i++) {
                for (int j = y; j < y + 8; j++) {
                    if (((i - x + j - y) % 2) == 0) {
                        if (arr[i][j] != 'B')
                            temp2++;
                    }

                    else {
                        if (arr[i][j] != 'W')
                            temp2++;
                    }
                }
            }
            //더 적게 칠한 횟수를 선택하고
            int res = temp1 < temp2 ? temp1 : temp2;
            if (res < count) count = res;   //결과에 저장
            temp1 = 0;
            temp2 = 0;
        }
    }
    printf("%d", count);

    return 0;
}