[백준] 1018번 체스판 다시 칠하기 - java[자바]

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

1018번: 체스판 다시 칠하기

 

문제

---

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

 

출력

---

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

예제 입력 1

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1

1

예제 입력 2

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

예제 출력 2

12

 

구현 전략

---

다들 난이도가 낮다는데 나는 왜이렇게 오래 걸렸는지...

좌표 평면을 이차원 배열로 다룰 때, 이중  for문 안에서 변수와 범위를 설정하는 게 자꾸 헷갈린다.

해결 전략은 그리 어렵지는 않다. 브루트포스로 풀면 괴상망측한 4중 for문이 나오기는 하지만 체스판 크기가 8X8로 고정되어 있기 때문에 시간 복잡도는 O(N*M)이다.

 

M * N 의 체스판이 주어지면, 그 안에서 만들 수 있는 8 * 8 체스판의 가짓수는 (M - 7) * (N - 7) 개이다.

예를 들어 N, M = 9 이면,

 이렇게 각각 정점(여기서 정점은 체스판의 가장 왼쪽 위의 좌표) (0, 0), (0, 1), (1, 0), (1, 1)에서 시작하는 체스판 4개를 만들 수 있다.

그리고 추가로 흰색 네모칸으로 시작하는 경우와 검은색 네모칸으로 시작하는 경우 두 가지가 존재하니, 총 (M -7) * (N - 7) * 2 개의 체스판에 대해 각각 다시 칠해야하는 정사각형의 수를 구한 뒤, 최소값을 갖는 경우를 리턴하면 된다.

 

우선 비교의 대상이 될 8 * 8 체스판을 만든다. 흰색으로 시작하는 경우와 검은색으로 시작하는 경우 두 가지가 있는데, 두 개를 다 만들었다.

색깔이 두 가지밖에 없으므로 흰색을 true, 검은색을 false로 하는 이차원배열로 선언한다.

static boolean[][] whiteBoard = makeInitBoard("W");
static boolean[][] blackBoard = makeInitBoard("B");

public static boolean[][] makeInitBoard(String color) {
    boolean[][] board = new boolean[8][8];
    boolean white = true;

    if (color.equals("W")) {    // 흰색으로 시작하는 경우
        for (int i = 0; i < 8; i++) {

            for (int j = 0; j < 8; j++) {
                board[i][j] = white;    // 첫번째 정사각형은 white
                white = !white;         // 한 줄에서는 색깔을 번갈아가면서 채운다
            }
            white = !white;             // 8 * 8 의 경우 줄바꿈을 하면서 색깔을 바꿔야한다.
        }
        return board;
    } else {    // 검은색으로 시작하는 경우
        for (int i = 0; i < 8; i++) {
            white = !white;
            for (int j = 0; j < 8; j++) {
                board[i][j] = white;
                white = !white;
            }
        }
        return board;
    }
}

체스판이 잘 만들어지는지, 간단하게 테스트 해봤다.

@Test
void getWhiteBoard() {
    boolean[][] whiteBoard = Main.makeInitBoard("W");
    assertThat(whiteBoard[0][0]).isEqualTo(true);
    assertThat(whiteBoard[1][0]).isEqualTo(false);
    assertThat(whiteBoard[2][0]).isEqualTo(true);
    assertThat(whiteBoard[3][0]).isEqualTo(false);
}

@Test
void getBlackBoard() {
    boolean[][] blackBoard = Main.makeInitBoard("B");
    assertThat(blackBoard[0][0]).isEqualTo(false);
    assertThat(blackBoard[1][0]).isEqualTo(true);
    assertThat(blackBoard[2][0]).isEqualTo(false);
    assertThat(blackBoard[3][0]).isEqualTo(true);
}

 

사용자 입력을 받아서 마찬가지로 이차원 배열을 만들어준다.

int height = sc.nextInt();
int width = sc.nextInt();
sc.nextLine();    // 개행문자 없애기용

boolean[][] inputBoard = getInputBoard(width, height);


public static boolean[][] getInputBoard(int width, int height) {
    boolean[][] result = new boolean[height][width];

    for (int i = 0; i < height; i++) {
        String input = sc.nextLine();

        for (int j = 0; j < width; j++) {
            if (input.charAt(j) == 'W') {
                result[i][j] = true;     // 마찬가지로 white이면 true, black이면 false
            } else {
                result[i][j] = false;
            }
        }

    }
    return result;
}

 

자 이제 만들 수 있는 모든 체스판에 대해, 새로 칠할 정사각형의 수를 구한다(getMappingCount). 각 경우의 수는 해당 체스판의 정점(가장 왼쪽 위 좌표)로 구분할 수 있다. (0, 0)부터 (N - 8, M - 8)까지의 경우에 수에 대해 값을 계산한다.

그리고 흰색과 검은색 체스판의 (0, 0)부터 (7, 7)까지 색깔과 각 경우의 수의 (정점, 정점)부터 (정점 + 7, 정점 + 7)의 색깔을 모두 비교하면서 다를 경우 count를 늘린다.

boolean[][] inputBoard = getInputBoard(width, height);
int result = 64;    // 최악의 경우
int endpointX = width - 8;
int endpointY = height - 8;

for (int y = 0; y <= endpointY; y++) {
    for (int x = 0; x <= endpointX; x++) {
        // 모든 경우 중 가장 작은 값 반환
        result = Math.min(result, getMappingCount(x, y, inputBoard));
    }
}

public static int getMappingCount(int x, int y, boolean[][] inputBoard) {
    int whiteCount = 0;
    int blackCount = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {

            if (whiteBoard[i][j] != inputBoard[y + i][x + j]) {
                whiteCount += 1;
            }
            if (blackBoard[i][j] != inputBoard[y + i][x + j]) {
                blackCount += 1;
            }
        }
    }
    // 각 경우에 대해 흰색으로 시작하는 경우와 검은색으로 시작하는 경우 중 작은 값 반환
    return Math.min(whiteCount, blackCount);
}

 

전체 코드

---

import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static boolean[][] whiteBoard = makeInitBoard("W");
    static boolean[][] blackBoard = makeInitBoard("B");

    public static void main(String[] args) {

        int height = sc.nextInt();
        int width = sc.nextInt();
        sc.nextLine();

        boolean[][] inputBoard = getInputBoard(width, height);
        int result = 64;
        int endpointX = width - 8;
        int endpointY = height - 8;

        for (int y = 0; y <= endpointY; y++) {
            for (int x = 0; x <= endpointX; x++) {
                result = Math.min(result, getMappingCount(x, y, inputBoard));
            }
        }

        System.out.println(result);
    }

    public static int getMappingCount(int x, int y, boolean[][] inputBoard) {
        int whiteCount = 0;
        int blackCount = 0;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {

                if (whiteBoard[i][j] != inputBoard[y + i][x + j]) {
                    whiteCount += 1;
                }
                if (blackBoard[i][j] != inputBoard[y + i][x + j]) {
                    blackCount += 1;
                }
            }
        }
        return Math.min(whiteCount, blackCount);
    }


    public static boolean[][] getInputBoard(int width, int height) {
        boolean[][] result = new boolean[height][width];

        for (int i = 0; i < height; i++) {
            String input = sc.nextLine();

            for (int j = 0; j < width; j++) {
                if (input.charAt(j) == 'W') {
                    result[i][j] = true;
                } else {
                    result[i][j] = false;
                }
            }

        }
        return result;
    }

    public static boolean[][] makeInitBoard(String color) {
        boolean[][] board = new boolean[8][8];
        boolean white = true;

        if (color.equals("W")) {
            for (int i = 0; i < 8; i++) {

                for (int j = 0; j < 8; j++) {
                    board[i][j] = white;
                    white = !white;
                }
                white = !white;
            }
            return board;
        } else {
            for (int i = 0; i < 8; i++) {
                white = !white;
                for (int j = 0; j < 8; j++) {
                    board[i][j] = white;
                    white = !white;
                }
            }
            return board;
        }
    }
}