[백준 실버 4] 1018번: 체스판 다시 칠하기

문제

https://www.acmicpc.net/problem/1018

 

풀이

• 체스판은 흰색과 검은색이 번갈아가면서 칠해져있어야 한다. 인접한 칸이 같은 색이면 안된다.
• N X M 크기의 보드를 8 X 8 사이즈로 잘라 체스판을 만드려고 한다.
• 이렇게 잘라서 만든 체스판은 색이 잘못된 경우 새로 칠하려고 한다.
• 자를 수 있는 체스판의 경우 중에서, 새로 칠하는 횟수가 가장 적은 경우의 최소 개수를 출력한다.

문제를 풀기 위해선 두 가지 포인트를 해결해야 한다.

첫째, N X M 사이즈의 보드를 어떻게 체스판 사이즈로 나눌 것인가.

둘째, 새로 칠하는 횟수를 어떻게 구해야 할 것인가.

 

첫째는 만들어질 수 있는 체스판의 경우의 수는 (N - 7) * (M - 7)이 된다.

(0,0)을 첫 번째 칸으로 가지는 체스판부터, (N - 8, M - 8)을 첫 번째 칸으로 가지는 체스판까지 모든 체스판을 고려한다.

 

둘째는 더 간단하다. 모든 체스판의 경우의 수는 두 가지이다. 첫 번째 칸이 검은색인 경우와 흰색인 경우이다. 이를 바탕으로 64의 칸이 모두 번갈아가며 색칠된 모습을 상상할 수 있다.

 

for (int i = 0; i < N; i++) {
    String line = br.readLine();
    for (int j = 0; j < M; j++) {
        // 흰색의 경우 true, 검은색의 경우 false
        if (line.charAt(j) == 'W') {
            board[i][j] = true;
        } else {
            board[i][j] = false;
        }
    }
}

board는 boolean형 2차원 배열이다. 흰색은 true, 검은색은 false로 저장한다.

 

int r = N - 7;
int c = M - 7;

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        check(i, j);
    }
}

만들어진 각 체스판의 첫 번째 칸을 i와 j로 나타낸다.

 

public static void check(int x, int y) {
    int count = 0;

    // 체스판의 첫번째 칸
    boolean first = board[x][y];

    for (int i = x; i < x + 8; i++) {
        for (int j = y; j < y + 8; j++) {

            if (board[i][j] != first) {
                count++;
            }

            first = !first;
        }

        first = !first;
    }

    // 8 X 8 경우의 수 중에서 맨 앞이 검정인 경우와 하양인 경우를 비교
    count = Math.min(count, 64 - count);

    min = Math.min(min, count);
}

check 메서드는 주어진 칸의 좌표를 기준으로 8 X 8 체스판을 만들어 탐색하며 새로 칠하는 칸의 개수를 구한다.

첫 번째 칸을 기준으로 다음 칸으로 이동하면 색을 반전시킨다. 또, 다음 줄로 이동했을 때 또한 색을 반전시켜 번갈아가면서 칠해진 체스판을 board의 칸과 비교한다. 만약 이상적인 체스판의 색과 다르다면 새로 칠해야 하는 칸이므로 count를 하나씩 올린다.

 

하나의 체스판은 색이 반전된 두 가지 경우로 칠할 수 있다. 그 말인즉슨, 두 가지 경우에서 색을 새로 칠하는 count 또한 완전히 반대가 된다는 뜻이다. 8 X 8 체스판의 색을 칠하는 최대 횟수는 64개이므로, 두 경우는 count와 64 - count가 되며, 둘 중 더 작은 쪽을 선택한다.

 

 

전체 코드 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static boolean[][] board;
	static int min = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		board = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String line = br.readLine();

			for (int j = 0; j < M; j++) {
				// 흰색의 경우 true, 검은색의 경우 false
				if (line.charAt(j) == 'W') {
					board[i][j] = true;
				} else {
					board[i][j] = false;
				}
			}
		}

		int r = N - 7;
		int c = M - 7;

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				check(i, j);
			}
		}

		System.out.println(min);
	}

	public static void check(int x, int y) {
		int count = 0;

		// 체스판의 첫번째 칸
		boolean first = board[x][y];

		for (int i = x; i < x + 8; i++) {
			for (int j = y; j < y + 8; j++) {

				if (board[i][j] != first) {
					count++;
				}

				first = !first;
			}

			first = !first;
		}

		// 8 X 8 경우의 수 중에서 맨 앞이 검정인 경우와 하양인 경우를 비교
		count = Math.min(count, 64 - count);

		min = Math.min(min, count);
	}

}

 

 

후기

단순히 사방탐색을 통해 비교하려는 어리석은 풀이법을 생각하다가 문제를 해결하는데 오래 걸렀다. 체스판의 특징을 좀 더 빨리 파악했다면 좋았을 것이다. 단순하게 푸는 것도 좋지만, 합리적인 풀이법을 떠올리는 게 중요하다는 생각이 들었다.