[C/C++] 체스판 다시 칠하기 (백준 1018)

문제

 

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

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

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

 

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

 

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

 

예제1

 

입력

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

출력

1

 

예제2

 

입력

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

출력

12

 

풀이

 

이 문제도 덩치 문제와 같이 한 번 풀었다가 실패하고 다시 풀어서 된 케이스다. 한 30분 정도 걸린 것 같다. 예시 1처럼 아예 8 8만 나오면 좋으련만... 예제 2와 같이 크게 나오면 잘라야하는데 이 자르는 부분이 이 문제의 키 포인트이다.

 

검수 자체는 간단하다 W와 B가 번갈아서 나오면 되기 때문에 번갈아가면서 검사하는 가장 쉬운법은 개인적으로 각 인덱스의 합이 짝수인가 홀수인가로 쉽게 나눌 수 있다고 생각하여 그렇게 풀었다.

 

여기서 문제는 자르는 방식인데 처음하려고 했던 생각부터 적어보려고 한다. 일단 방식은 비슷했다.

 

 

일단 10 13의 판에서 88을 잘랐을 때 주황색 부분이 88부분이 된다. 그리고 그 부분의 처음을 갈색으로 칠했다. 그리고 다음 예시로

 

 

이런 모양도 될 수 있다. 여기서 가장 처음 부분은 왼쪽 위로 되어있다. 이 갈색 부분만 모아보니...

 

 

이렇게 특정이 되었다. 10 - 8, 13 - 8 의 [0][0] 에서 [2][5]의 범위가 특정되어서 이걸 숙지한 상태로 하면 되는데 처음에는 temp라는 가상의 2차원 배열을 만들어서 저 2차원 배열을 순회하면서 temp에 2차원 배열을 넣어서 또 그걸 비교하려고 하니 내가 만들어놓은 함수 포함해서 총 6번의 중첩 for문이 나오게 되어 바로 시간초과가 났다...

 

그런식으로 코드 짜면서도 이게 맞나 싶었지만 역시 아니었다. 알고보니 for문을 쓸데없이 많이 사용해서 그런 결과가 나온거라서 for문을 두 개 줄이고 해보니 해결되었다. 코드를 간결하게 짜는 건 확실히 중요한것 같다.

 

코드

 

#include <iostream>

int check_repair(char **a, int start_x, int start_y){
    int answer = 0;
    for(int i = start_x ; i < start_x + 8 ; i++){ //자른 범위를 정해서 계산
        for(int j = start_y ; j < start_y + 8 ; j++){
            if(( i + j ) % 2 == 0 && a[i][j] != 'W'){
                answer++;
            }
            else if(( i + j ) % 2 == 1 && a[i][j] != 'B'){
                answer++;
            }
        }
    }
    return (64 - answer) > answer ? answer : (64 - answer);
} //홀수와 짝수 중 최소값을 찾아주는 함수

int main(void){
    int x, y, check_x, check_y;
    scanf("%d %d", &x, &y);
    char **array = new char*[x];
    for(int i = 0 ; i < x ; i++){
        array[i] = new char[y];
    }

    for(int i = 0 ; i < x ; i++){
        scanf("%s", array[i]);
    }
    //배열 초기화

    check_x = x - 8;
    check_y = y - 8;
    int min = 64;

    for(int i = 0 ; i <= check_x ; i++){
        for(int j = 0 ; j <= check_y ; j++){
            int min_temp = check_repair(array, i, j); //비교 연산
            if(min > min_temp)
                min = min_temp;
        }
    } //최솟값 구하기

    printf("%d", min);
}