백준 1018 : 체스판 다시 칠하기

 

문제 바로 가기

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

 

접근 방법

 

Step1. 체스판 자르기

문제에서 주어진 체스판의 크기는 항상 8 x 8 사이즈가 아니기 때문에, 8 x 8 이상의 크기를 가지는 체스판이라면 해당 체스판에서 나올 수 있는 체스판의 종류는 여러 가지가 나올 수 있다.

가령 9 x 9 크기의 체스판이 있다면 이는 아래와 같이 4가지 버전으로 나누어질 수 있다.

우리가 필요한 것은 위의 4가지 버전의 체스판 중에서 가장 적게 다시 칠해도 되는 체스판을 선택하는 것이다.

즉, 각각의 체스판에서 다시 칠해야 할 칸 수를 세어보고, 다음 체스판에서 다시 칠해야 할 칸 수와 비교해보면서 모든 체스판을 비교해야 하는 브루트 포스 접근이 필요한 것이다.

 

Step 2. 체스판의 최소 재도색 칸 수 구하기

위의 4가지 버전에서 최소로 재도색할 칸 수를 구할 때 각 버전 별로 고려해야 할 사항이 또 있다.

체스판의 첫 줄은 검정색으로 시작할 수도 있고, 흰색으로 시작할 수도 있다. 그리고 첫 줄이 검정색으로 시작했다면, 다음 줄은 반드시 흰색으로 시작해야 한다.

2 x 2 사이즈의 체스판을 그림으로 그려서 이해해보자.

현재 상태가 위의 그림에서 2번째 예시와 같은 상태라고 하면, 체스판의 첫 행이 Black과 White으로 시작하는 체스판으로 만들기 위해서는 총 1개의 칸만 다시 칠하면 된다.

반면, 체스판의 첫 행이 White와 Black으로 시작하는 체스판으로 만들기 위해서는 총 3개의 칸을 다시 칠하면 된다.

이렇게 2개의 케이스에 대해서 비교를 해서 최솟값을 구하면 되는데, 규칙을 찾을 수도 있다.

Black White로 시작하는 체스판에서 다시 칠해야 하는 칸의 개수(e.g., 1칸)를 전체 체스판의 크기(e.g., 4칸)에서 빼면 White Black으로 시작하는 체스판에서 다시 칠해야 하는 칸의 개수(e.g., 3칸)와 일치한다.

이러한 규칙을 적용한다면 조금 더 코드를 간결하게 작성할 수 있게 된다.

 

Step 3. 코드로 구현하기

위에서 다룬 내용들을 코드로 구현하면 아래와 같이 작성할 수 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 행의 개수
        int M = Integer.parseInt(st.nextToken()); // 열의 개수
        String[] board = new String[N];// 주어진 원본 보드

        // 보드 채우기
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine();
        }

        // 접근법의 Step 1 파트와 대응된다.
        int minRepaints = Integer.MAX_VALUE;
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                // 각 위치에서 8 x 8 체스판 확인
                minRepaints = Math.min(minRepaints, calculateRepaints(board, i, j));
            }
        }

        bw.write(minRepaints + "\n");

        br.close();
        bw.close();
    }

    private static int calculateRepaints(String[] board, int startRow, int startCol) {
        String[] boardType = {"WBWBWBWB", "BWBWBWBW"};
        int repaints = 0;

        // 매개변수로 받은 시작점에서부터 체스판을 확인하며 다시 칠해야 할 칸의 개수를 확인한다.
        for (int i = 0; i < 8; i++) {
            int row = startRow + i;
            for (int j = 0; j < 8; j++) {
                int col = startCol + j;
                // 모듈로 연산을 통해서 WB로 시작하는 행에서 비교를 했다면
                // 다음 비교는 BW로 시작하는 행에서 비교를 할 수 있도록 한다.
                if (board[row].charAt(col) != boardType[row % 2].charAt(j)) {
                    // boardType에 대해서 charAt에 charAt(j)가 아닌 charAt(col)을 하면 틀린다.
                    // 처음 입력 받은 board에 대해서 charAt(col)을 하는 것과
                    // 변하지 않는 boardType의 값을 기준으로 인덱스를 비교하는 것은
                    // charAt에 들어갈 인덱스의 값이 달라야 한다.
                    repaints++;
                }
            }
        }
        // [Step 2에서 다룬 규칙]
        // 체스판의 최상단 row가 bw로 시작하는 타입일 때 다시 칠해야 하는 타일의 최소 개수가 x개라면
        // wb로 시작하는 타입에서 다시 칠해야 하는 타일의 최소 개수는 (전체 체스판의 타일 개수) - x 개가 된다.
        // 따라서 이렇게 2개 타입의 체스판 중 최소로 칠해야 하는 개수가 나오는 것을 선택할 수 있도록 한다.
        return Math.min(repaints, 64 - repaints);
    }
}

 

Reference.