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

문제 설명

 

1018번: 체스판 다시 칠하기

 

접근 방법

입력으로 주어진 M * N 크기의 보드로부터 8 * 8 크기 만큼 잘라 체스판을 구해야 하는데, 이때 구한 체스판은 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 만일 잘랐던 체스판이 위 조건을 충족하면 별도로 색칠할 필요 없지만, 그렇지 않다면 최소 횟수로 다시 색칠해야 한다.

 

처음 이 문제에 접근했던 방법으로는 M * N 크기의 보드로부터 8 * 8 크기 만큼 잘라 해당 2차원(8 * 8) 배열을 탐색하면서 "첫 번째 요소가 그 다음 요소와 중복되는지" 일일이 검사했었다. 하지만 이러한 방법으로 문제에서 요구하는 조건을 완전하게 충족시키면서 탐색 알고리즘을 구현하기가 상당히 어려운 점이 많았다. 그래서 발상의 전환이 필요했다.

 

생각해보면 조건을 충족하는 체스판은 딱 두 가지밖에 없는데,(사실 문제 설명에 힌트가 명시되어 있었다.) 자바 코드로 2차원 문자 배열로 나타내면 다음과 같다.

 

    static char[][] standardBoard1 = new char[][]{
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
    };

    static char[][] standardBoard2 = new char[][]{
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
    };

 

즉,  M * N 크기의 보드로부터 8 * 8 크기 만큼 잘라 해당 2차원(8 * 8) 배열을 탐색하는 것까지는 좋지만, 굳이 "첫 번째 요소가 그 다음 요소와 중복되는지" 일일이 검사할 필요 없이 위 2개의 올바른 체스판과 비교하면서 색칠해야하는 횟수를 카운팅(counting)하기만 하면 됐었던 것이다.

 

 

전체 소스 코드

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

class Main {

    static char[][] standardBoard1 = new char[][]{
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
    };

    static char[][] standardBoard2 = new char[][]{
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
        {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
        {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        char[][] chaseBoard = new char[n][m];
        for (int i = 0; i < n; i++) {
            chaseBoard[i] = br.readLine().toCharArray();
        }

        int result = 2500, countOfPrinting1 = 0, countOfPrinting2 = 0;

        for (int i = 0; i < n - 7; i++) {
            for (int j = 0; j < m - 7; j++) {

                for (int k = i, a = 0; k < 8 + i; k++, a++) {
                    for (int l = j, b = 0; l < 8 + j; l++, b++) {
                        if (chaseBoard[k][l] != standardBoard1[a][b]) {
                            countOfPrinting1++;
                        }
                        if (chaseBoard[k][l] != standardBoard2[a][b]) {
                            countOfPrinting2++;
                        }
                    }
                }

                result = Math.min(result, Math.min(countOfPrinting1, countOfPrinting2));
                countOfPrinting1 = 0;
                countOfPrinting2 = 0;
            }
        }

        System.out.println(result);
    }
}

 

 

참고자료

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