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

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

1018번: 체스판 다시 칠하기

 

예제 입력은 추가로 더 있으나 모두 첨부하면 늘어질 것 같아 생략한다.

 

8x8 크기의 체스판을 만드려고 하는데, 사이즈가 다를 수도 있고, 검정, 흰색의 배치가 엉망일 수도 있다.

하여 주어진 보드에서 체스판으로 만들려면 변경해야 되는 색의 최소 개수를 정하면 된다.

 

우선 위의 사진 처럼 8x8 사이즈로만 자르면 된다.

(3개만 만든 이유는 귀찮아서이다.. 참고만 하길)

 

그리고 체스판을 만들 때 좌상단이 흰색인 경우, 검정색인 경우 총 두 가지의 패턴이 존재한다.

아무 패턴으로나 변경하는데 규칙이 있는데,

 

규칙이 보이는가?

좌상단이 검정색인 패턴 : B

좌상단이 하얀색인 패턴 : W

B가 될 때 변경되는 색의 수를 구하면 W가 될 때 변경되는 색의 수를 알 수 있다.

체스판의 크기에서 변경되는 색의 수를 뺴면 다른 패턴의 변경되는 수를 알 수 있다.

 

이 사실을 이용하여 문제의 최소값을 구할 때 사용할 것이다.

 

주어지는 board의 크기는 상수가 아니고 만들어야 될 originBoard의 크기는 (8x8)상수이기 때문에

N, M에서 -8을 빼준만큼 기준값으로 두어 for문을 반복하여 움직이며 originBoard와 board를 비교하면 된다.

originBoard와 board를 비교할 때 originBoard를 B_PATTERN으로 할지, W_PATTERN으로 할지는 자기가 하고 싶은 거로 하면 된다.

필자는 포켓몬스터의 레시라무를 좋아해서 W_PATTERN으로 할 것이다.

기회가 된다면 한 번 찾아보길 추천한다.

진짜 멋있따.

 

아래 코드를 첨부하였다.

설명이 필요할 것 같은 부분에 주석을 달아 놓았으니 궁금한 부분이 있다면 댓글로 물어보면 답변하도록 하겠다.

 

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

public class Main {

    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static String board[];
    private static final int boardSize = 64;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());

        // input 받은 값으로 체스판 만들기;
        board = new String[row];
        for (int i = 0; i < row; i++) board[i] = bf.readLine();

        // 체스판 자르기;
        // row, col이 어떻게 오던지 간에 8x8 크기의 체스판을 만들어야 하기 때문에
        int getSol = 0;
        int sol = Integer.MAX_VALUE;
        for (int i = 0; i <= row - 8; i++) {
            for (int j = 0; j <= col - 8; j++) {
                getSol = getSolution(i, j);
                if (sol > getSol) sol = getSol;
            }
        }

        bw.write(String.valueOf(sol));
        bw.flush();
        bw.close();
    }

    private static int getSolution(int startRow, int startCol) {
        String[] originWhiteBoard = {"WBWBWBWB", "BWBWBWBW"};
        int whiteSol = 0;

        // row, col을 다시 만들어준 이유는 입력 받은 board에서 계속 잘라가며 originBoard와 비교해야 되기 떄문.
        for (int i = 0; i < 8; i++) {
            int row = startRow + i;
            for (int j = 0; j < 8; j++) {
                int col = startCol + j;
                // originBoard를 2줄만 만들었기에 홀/짝수로만 가져오도록 한다.
                if (board[row].charAt(col) != originWhiteBoard[i % 2].charAt(j)) whiteSol++;
            }
        }
        int blackSol = boardSize - whiteSol;
        return Math.min(whiteSol, blackSol);
    }
}