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

🔒 문제

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

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

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

⌨ 입력

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

🖨 출력

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

📚 예제

Ex1)

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

1

Ex2)

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

12

Ex3)

8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

0

Ex4)

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

31

Ex5)

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB

0

Ex6)

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

2

Ex7)

11 12
BWWBWWBWWBWW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBWWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW

15

📌 풀이

문제에서 알려주는 것 그대로 하면된다.

일단 주어진 행열에서 8 * 8 크기로 잘라내는 모든 경우의 수를 생각해내고 그 체스판에서

시작점이 B인것과 W인것 두개로 나눠서 바꿔야할 갯수를 구하고 그 중 작은 값을 도출한다.

🔑 c언어 코드

#include <stdio.h>

int count(char** ary, int M, int N); // 답찾기
int compare(char** ary, int i, int j, char B); // 첫 칸이 B 거나 W인 경우의 바꿔야할 개수 구하기

int main()
{
    int M, N, ans; // ans는 답

    scanf("%d %d", &M, &N);
    // 문자열 2차원 동적 배열
    char** ary = (char**)malloc(sizeof(char*) * M); 
    for (int i = 0; i < M; i++)
        ary[i] = (char*)malloc(sizeof(char) * (N + 1));
    // 문자열 대입
    for (int i = 0; i < M; i++)
        scanf("%s", ary[i]);
    ans = count(ary, M, N);

    printf("%d", ans);

    return 0;
}

int count(char** ary, int M, int N)
{
    int ans = 33;
    int k;
    int r1, r2;


    for (int i = 0; i <= M - 8; i++) // 8행씩 지켜보려고
        for (int j = 0; j <= N - 8; j++) // 8열씩 지켜보려고
        {
            k = 0;
            // 8X8 배열에서 검은색과 흰색 개수 구하기
            r1 = compare(ary, i, j, 'B');
            r2 = compare(ary, i, j, 'W');

            if (r1 > r2)
                k = r2;
            else
                k = r1;

            if (ans > k)
                ans = k;
        }

    return ans;
}
int compare(char** ary, int i, int j, char B)
{
    int k = 0;

    for (int a = i; a < i + 8; a++)
        for (int b = j; b < j + 8; b++)
        {
            if ((a % 2 == i % 2) && (b % 2 == j % 2)) // 8*8 체스판에서 홀수행,홀수열
            {
                if (ary[a][b] != B)
                    k++;
            }
            else if ((a % 2 == i % 2) && (b % 2 != j % 2)) // 8*8 체스판에서 홀수행,짝수열
            {
                if (ary[a][b] == B)
                    k++;
            }
            else if ((a % 2 != i % 2) && (b % 2 == j % 2)) // 8*8 체스판에서 짝수행,홀수열
            {
                if (ary[a][b] == B)
                    k++;
            }
            else // 8*8 체스판에서 짝수행,짝수열
            {
                if (ary[a][b] != B)
                    k++;
            }

        }

    return k;
}

코드가 많이 복잡한데 더 정리되면 간단하게 다시 짜보겠다.