[알고리즘] 체스판 다시 칠하기 (백준 1018)

사연

취업준비를 하면서 코딩테스트 공부를 하고있다.

문제

백준 1018문제이다. 체스판 다시 칠하기 문제인데 체스판은 8 * 8로 자를 수 있고 체스판은 검은색, 흰색 두가지로 칠해져 있는데 무작위로 칠해져있다. 이 것을 올바른 체스판(검은색, 흰색이 서로 인접하지 않고 엇갈리는, 우리가 흔히 아는 형태의 체스판)으로 만들기 위해 색을 칠해야 하는데 최소의 횟수로 색을 칠하는 횟수를 구하는 문제...

백준 1018 체스판 다시칠하기 링크

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    private static class Position {
        private int y;
        private int x;
        private String expected;

        public Position(int y, int x, String expected) {
            this.y = y;
            this.x = x;
            this.expected = expected;
        }
    }

    private static int minReDrawMakeChessBoard(String[][] grid, String startChar, int[] chopAreaStartPosition, int[] chopAreaEndPosition) {
        int[] dy = {1, 0};
        int[] dx = {0, 1};

        int chopAreaStartY = chopAreaStartPosition[0];
        int chopAreaStartX = chopAreaStartPosition[1];
        int chopAreaEndY = chopAreaEndPosition[0];
        int chopAreaEndX = chopAreaEndPosition[1];

        boolean[][] visited = new boolean[grid.length][grid[0].length];
        Queue<Position> reserved = new LinkedList<>();

        reserved.add(new Position(chopAreaStartY, chopAreaStartX, startChar));
        visited[chopAreaStartY][chopAreaStartX] = true;

        int draw = 0;

        while (!reserved.isEmpty()) {
            Position poll = reserved.poll();
            int y = poll.y;
            int x = poll.x;
            String expected = poll.expected;

            // matched
            boolean matched = expected.equals(grid[y][x]);
            if (!matched) {
                draw++;
            }

            for (int i = 0; i < 2; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];
                String nextCharExpected = expected.equals("W") ? "B" : "W";
                if (nextY <= chopAreaEndY && nextX <= chopAreaEndX) {
                    if (!visited[nextY][nextX]) {
                        reserved.add(new Position(nextY, nextX, nextCharExpected));
                        visited[nextY][nextX] = true;
                    }
                }
            }

        }
        return draw;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] boardSize = bufferedReader.readLine().split(" ");

        int ROWS = Integer.parseInt(boardSize[0]);
        int COLS = Integer.parseInt(boardSize[1]);

        String[][] grid = new String[ROWS][COLS];

        for (int i = 0; i < ROWS; i++) {
            String[] columns = bufferedReader.readLine().split("");
            grid[i] = columns;
        }

        int[] chopAreaStartPoint = {0, 0};
        int[] chopAreaEndPoint = {7, 7};

        Integer minReDraw = null;

        while (chopAreaEndPoint[0] < ROWS && chopAreaEndPoint[1] < COLS) {
            int chopAreaStartY = chopAreaStartPoint[0];
            int chopAreaStartX = chopAreaStartPoint[1];
            int chopAreaEndY = chopAreaEndPoint[0];
            int chopAreaEndX = chopAreaEndPoint[1];

            int w = minReDrawMakeChessBoard(grid, "W", chopAreaStartPoint, chopAreaEndPoint);
            int b = 64 - w;
            int currentMinDraw = Math.min(w, b);

            if (minReDraw == null) {
                minReDraw = currentMinDraw;
            } else {
                minReDraw = Math.min(minReDraw, currentMinDraw);
            }

            int nextEndX = chopAreaEndX + 1;
            if (nextEndX < COLS) {
                chopAreaStartPoint = new int[]{chopAreaStartY, chopAreaStartX + 1};
                chopAreaEndPoint = new int[]{chopAreaEndY, nextEndX};
            } else {
                chopAreaStartPoint = new int[]{chopAreaStartY + 1, 0};
                chopAreaEndPoint = new int[]{chopAreaEndY + 1, 7};
            }
        }

        System.out.println(minReDraw);
    }

}

코드설명

먼저 startPosition {0,0}, endPosition {7,7}의 영역으로 부터 체스판을 자르기 시작해서 endPosition이 grid의 마지막에 다다를때까지 계속 자르며 가장 적은수로 색을 칠하는 횟수가 무엇인지 구한다.

매번 잘라서 횟수를 구할때 bfs탐색을 통하여 구하고 무한 반복을 방지하기 위해 visited 배열을 초기화해서 이미 방문한 곳은 방문하지 않는다.

매번 체스판을 8 8로 잘라서 최소 색칠횟수를 구할때 처음에 'W'로 시작하는 경우와 'B'로 시작하는 경우를 구해아한다. 하지만 'W'로 시작하는 체스판의 최소 색칠횟수를 구했으면 8 8 = 64에서 그 값을 빼면 나머지 'B'로 시작하는 경우가 나온다.

Position이라는 클래스를 통해 현재 좌표와 다음에 어떤 색을 칠해야만 하는지 (검은색이면 힌색, 흰색이면 검은색) 저장하고 다음번에 Queue에서 가져와서 실제 grid에 칠해져있는 값과 비교한후 기대한 값이 아니면 draw의 값을 하나씩 더해준다

Math.min(int n1, int n2) 를 활용해 계속해서 누적해서 작은 값을 저장한다.