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

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

이 문제는 반례가 상당히 많았다.
문제에 나온 예제들로 문제가 발견되지 않았음에도 제출을 하면 실패로 뜨곤 했다.

브루트 포스를 이용하는 만큼 모든 경우의 수를 다 따져봐야한다. 그렇기 때문에 예제에서도 반영되지 않았던 경우의 수가 수도 없이 많았다. 이 문제에서 경우의 수는 여러 갈래가 있다.

1. 첫 칸을 칠하느냐? 마느냐?

문제에서도 언급되었다시피, 이 체스판을 색칠하는 경우는 맨 위쪽 위 칸이 흰색인 경우와 검은색인 경우 뿐이다. 나는 이 문제를 풀 때 첫 칸을 기억해놓고 그 칸과 붙어있는 칸이 같은 색이면 바꾼다고 가정하고 카운트를 늘리는 식으로 알고리즘을 작성했다. 그런데 가장 첫 칸을 그 색 그대로 기억해두는 것 외에도 첫 칸을 바꿔버리는 경우의 수 역시 존재한다.

BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

이런 경우에는 처음 작성한 코드로는 첫 칸을 제외한 모든 칸을 칠해버리는 값이 나왔다.
하지만 첫 칸 하나만 칠하면 다른 칸을 칠할 필요가 없으니 최솟값은 1이 된다.
그래서 첫 칸을 그대로 둔 것과 첫 칸을 칠한 것으로 경우를 나눠서 각자의 최솟값을 따로 구했다.

2. 넓은 체스판에서 8x8 만큼 떼는 경우의 수

이 경우는 잘 생각해보면 쉽다.
최소 길이는 가로x세로 8x8인데 이를 넘어선 경우에는 넘어선 길이 만큼의 경우의 수가 더 발생한다. 이는 (가로 - 7) * (세로 - 7)개 이다.
예를 들어 가로x세로 10x12를 받았다면 이 안에서 만들 수 있는 8x8 체스판의 수는

(10-7) * (12-7) = 15개 이다.

모든 경우의 수를 고려하기 위해 반복문을 이용해 이차원 배열에서 가로로 (가로-7)만큼, 세로로(세로-7)만큼 시작점을 1씩 늘려주며 돌리면 모든 체스판을 떼는 경우의 수만큼 돌릴 수 있다.

3. 세로로 같을 때

가로로 같은 경우를 먼저 생각하기 쉬운데, 세로도 잘 생각해봐야 한다.
물론 세로로 첫 번째 칸(j=0)만 비교하고 나면 나머지는 비교할 필요가 없다. (어차피 옆 칸 고려하면서 다 바뀌기 때문)
필자는 세로 첫 번째 칸은 따로 ch2에 구분하여 두었다가 줄이 넘어가면 이를 비교하는 식으로 경우의 수를 따지는데 성공했다.

4. 처음 두 칸이 같고 그 이후가 다를 때

이 반례에서 유일하게 실패가 계속 떴었다.
예제에는 이 반례가 존재하지 않았기 때문. 대표적으로

BBWBWBWW
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
WWBWBWBB

이 경우에서 답은 6이지만 필자는 계속 8이 떴던 것.
그 이유를 알고 보니 첫 칸을 칠하는 경우의 수에서 다음 칸을 이동할 때 다음 칸을 칠해버리는 오류가 있었고 이를 찾는데만 1시간이 걸렸다. 디버깅 모드로 한줄한줄 천천히 따라가며 돌리다보니 찾을 수 있었다.
반례와 디버깅의 중요성을 알게 되는 순간이었다...

결과

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n1 = Integer.parseInt(st.nextToken()), n2 = Integer.parseInt(st.nextToken());
		char [][] chess = new char[n1][n2];

		for(int i = 0; i < n1; i++) {
			String st2 = bf.readLine();
			for(int j = 0; j < n2; j++) {
				chess[i][j] = st2.charAt(j);
			}
		}
		
		int min = Integer.MAX_VALUE;
		
		for(int a = 0; a < (n1 - 7); a++) {
			for(int b = 0; b < (n2-7); b++) {
				char ch2 = chess[a][b];
				int count = 0;
				int count2 = 1;
				
				for(int i = 0; i < 8; i++) {
					char ch = chess[i+a][b];
					for(int j = 0; j < 8; j++) {
						if(j==0 && i!=0 && ch == ch2) {
							count++;
							if(ch2 == 'B') {
								ch2 = 'W';
								ch = ch2;
							}
							else  {
								ch2 = 'B';
								ch = ch2;
							}
						}
						else if(j==0 && i!=0 && chess[i+a][b] != ch2) {
							ch2 = chess[i+a][b];
							ch = ch2;
						}
						else if(j!=0 && chess[i+a][j+b]==ch) {
							count++;
							if(ch == 'B') {
								ch = 'W';
							}
							else ch = 'B';
						}
						else {
							ch = chess[i+a][j+b];
						}
					}
				}
				
				char ch = chess[a][b];
				
				if(ch == 'B') ch = 'W';
				else ch = 'B';
				
				ch2 = ch;
				
				for(int i = 0; i < 8; i++) {
					if(i!=0) ch = chess[i+a][b];
					for(int j = 0; j < 8; j++) {
						if(j==0 && i!=0 && ch == ch2) {
							count2++;
							if(ch2 == 'B') {
								ch2 = 'W';
								ch = ch2;
							}
							else  {
								ch2 = 'B';
								ch = ch2;
							}
						}
						else if(j==0 && i!=0 && ch != ch2) {
							ch2 = ch;
						}
						else if(j!=0 && chess[i+a][j+b]==ch) {
							count2++;
							if(ch == 'B') {
								ch = 'W';
							}
							else ch = 'B';
						}
						else if(i==0 && j==0) {
							continue;
						}
						else {
							ch = chess[i+a][j+b];
						}
					}
				}
				
				if(min > count) min = count;
				if(min > count2) min = count2;
			}
		}
		bw.write(String.valueOf(min));
		
		bw.flush();
		bw.close();
	}

}

코드를 줄일 여지나 개선할 여지는 얼마든지 있다.
이 글을 보게 되는 사람이 있다면 부디 그대로 사용하지 말고 참고만 해줬으면 한다.