[TIL-25/02/03] 99클럽 코테 스터디 11일차 - 백준 1018: 체스판 다시 칠하기- JAVA

https://www.acmicpc.net/problem/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

 

문제접근 

입력으로 주어지는 보드의 크기 N, M이 비교적 작기 때문에 완전 탐색(브루트 포스)으로 해결할 수 있다.

 

문제의 조건을 우선 살펴보자.

체스판을 올바르게 만들 수 있는 경우는 두 가지뿐이다

(1) 맨 왼쪽 위 칸이 'W'인 경우, (2) 맨 왼쪽 위 칸이 'B'인 경우

 

따라서 주어진 `NxM`보드에서 모든 `8x8`크기의 부분을 선택하여, 두 경우 각각 필요한 수정 횟수를 계산한 후 최소값을 찾는다.

 

탐색방법으론 `boolean` (`true = B`, `false = W`)을 사용한다. 문자나 문자열도 방법이지만 가능 쉽게 접근 할 수 있다고 생각했다.

• 이중 루프를 사용하여 모든 가능한 8×8 크기의 체스판을 탐색한다.
• 현재 탐색 중인 8×8 부분에서 체스판 규칙을 유지하도록 바꿔야 하는 칸의 개수를 계산한다.

 

칠해야 하는 횟수 계산 방법

• 첫 번째 칸의 색을 기준(start)으로 정하고, 해당 칸에서 시작하는 올바른 체스판 패턴을 유지해야 한다.
• 가로 방향(→): 이전 칸과 다른 색이 되어야 한다. 만약 같은 색이면 count++하고 색을 반대로 바꾼다.
• 세로 방향(↓): 위쪽 행과 반대 색으로 시작해야 한다. 따라서 새 행의 첫 칸을 기준으로 색을 변경한다.
• count 값과 (8×8 - count) 값을 비교하여 더 적은 횟수로 수정할 수 있는 경우를 선택한다.

모든 가능한 8×8 체스판을 검사하면서 최소 칠하기 횟수를 최신화한다.

 

코드

package backjoon.silver.lv4;

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

public class B1018 {
    public static final int SIZE = 8;
    static boolean[][] board;

    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());
        int M = Integer.parseInt(st.nextToken());

        board = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String ary = br.readLine();
            for (int j = 0; j < M; j++) {
                if (ary.charAt(j) == 'B') {
                    board[i][j] = true;
                }
            }
        }

        int min = Integer.MAX_VALUE;

        // 모든 8x8을 탐색할 수 있는 조건
        for (int i = 0; i + SIZE <= N; i++) {
            for (int j = 0; j + SIZE <= M; j++) {
                // 체크판을 칠하는 조건 카운터
                min = Math.min(min, countChangedColor(i , j));
            }
        }

        System.out.println(min);
    }

    private static int countChangedColor(int r_start, int c_start) {
        int r_end = r_start + SIZE;
        int c_end = c_start + SIZE;

        boolean firstColor = board[r_start][c_start];
        int count = 0;

        for (int i = r_start; i < r_end; i++) {
            boolean color = firstColor;

            for (int j = c_start; j < c_end; j++) {
                if (board[i][j] != color) {
                    count++;
                }
                color = !color;
            }

            firstColor = !firstColor;
        }

        return Math.min(count, (SIZE * SIZE) - count);
    }
}

 

 

코드 분석

1. 입력처리

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

• 빠른 입력 처리를 위해 BufferedReader를 사용
• StringTokenizer를 사용하여 공백을 기준으로 N과 M을 읽음

 

2. 체스판 입력을 `boolean`배열에 저장

board = new boolean[N][M];

for (int i = 0; i < N; i++) {
    String ary = br.readLine();
    for (int j = 0; j < M; j++) {
        if (ary.charAt(j) == 'B') {
            board[i][j] = true;
        }
    }
}

• 'B'는 `true`, 'W'는 `false`로 변환하여 저장
• 'W'는 기본적으로 `false`이므로 따로 처리하지 않아도 됨(기본형의 default 값)
• 문자열을 `charAt(j)`로 직접 탐색하여 불필요한 문자열 변환을 줄임 (효율적)

 

3.  8×8 모든 부분 탐색 (완전 탐색)

int min = Integer.MAX_VALUE;

// 모든 8x8을 탐색할 수 있는 조건
for (int i = 0; i + SIZE <= N; i++) {
    for (int j = 0; j + SIZE <= M; j++) {
        // 체크판을 칠하는 조건 카운터
        min = Math.min(min, countChangedColor(i , j));
    }
}
System.out.println(min);

`i + SIZE <= N` 및 `j + SIZE <= M` 조건을 사용하여 범위를 벗어나지 않도록 해야한다.

각 영역마다 구해진 최소카운팅 중 가장 최소값을 찾는게 문제이다.

 

4.  8×8 체스판을 체크하여 다시 칠해야 하는 횟수 계산

private static int countChangedColor(int r_start, int c_start) {
    int r_end = r_start + SIZE;
    int c_end = c_start + SIZE;

    boolean firstColor = board[r_start][c_start];
    int count = 0;

    for (int i = r_start; i < r_end; i++) {
        boolean color = firstColor;

        for (int j = c_start; j < c_end; j++) {
            if (board[i][j] != color) {
                count++;
            }
            color = !color;
        }

        firstColor = !firstColor;
    }

    return Math.min(count, (SIZE * SIZE) - count);
}

• `firstColor = board[r_start][c_start]`: 현재 8×8의 시작 색 저장
• `boolean color = firstColor`: 현재 탐색 중인 칸이 유지해야 할 색
• `if (board[i][j] != color) count++;`
  • 현재 칸이 올바른 색이 아니면 칠해야 하므로 `count++`
• `color = !color;`
  • 다음 칸은 반대 색이 되어야 하므로 색을 반전
• `firstColor = !firstColor;`
  • 다음 행의 첫 번째 칸은 이전 행의 첫 번째 칸과 반대 색이어야 함

 

여기서 `(SIZE * SIZE) - count`를 사용하여 첫 칸이 반대 색일 때의 경우도 고려해서 최소값을 구하도록 한다.