[Silver IV][JAVA] 1018번:체스판 다시 칠하기

각 칸이 흰색 또는 검은색으로 칠해진 커다란 판에서 임의의 위치부터 8x8크기로 잘라 체스판을 만든다. 그 중 가장 적은 칸을 칠하여 체스판을 만들고자 할 때, 칠해야하는 최소값을 구하는 문제. 하나하나 비교해서 풀이

위 처럼 NxM의 배열에서 무작위 8x8크기의 배열을 뽑아내야한다.

10x10짜리 배열을 기준으로, 해당 판에서 8x8배열을 선택하는 경우의 수는 총 9가지이며, 이를 도식화하면 위 그림과 같다.

전체 배열에서 8x8만큼 한 칸씩 이동하여 비교하면 된다.

for (int n = 0; n < N - 7; n++)
{
	for (int m = 0; m < M - 7; m++)
	{
		// TODO
	}
}

위 코드와 같이 기술하면 가로부터 한 칸씩 이동하며, 끝에 도달할 경우 세로로 한 칸 이동한 뒤 다시 가로부터 한 칸씩 이동할 것이다. n < N - 7인 이유는 비교할 배열의 세로 길이가 8이기 때문.

체스판에는 두 가지 경우의 수가 있다.

체스판의 상단 좌측을 기준으로 하얀색으로 시작하는 판과, 검은색으로 시작하는 판으로 두 가지가 존재한다. 하얀색을 true, 검은색을 false로 치환하여 하얀색 체스판과 검은색 체스판을 만들어 비교할 것이다.

// 상단 좌측이 하얀색으로 시작하는 체스판
private static final boolean[][] WHITE = {
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
};

// 상단 좌측이 검은색으로 시작하는 체스판
private static final boolean[][] BLACK = {
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
};

전체소스

package baekjoon_java.SilverIV;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 백준 전체 1018 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/26/a1018">1018 풀이</a>
 * @since 2023.09.06 Wed 02:03:20
 */
public class 체스판다시칠하기 {
    // 상단 좌측이 하얀색으로 시작하는 체스판
    private static final boolean[][] WHITE = {
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
    };

    // 상단 좌측이 검은색으로 시작하는 체스판
    private static final boolean[][] BLACK = {
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
    };

    // 체스판
    private static boolean[][] board;

    /**
     * 메인 함수
     *
     * @param args: [String[]] 매개변수
     * @throws IOException 데이터 입출력 예외
     */
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] temp = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // 세로 길이
        int N = temp[0];

        // 가로 길이
        int M = temp[1];

        board = new boolean[N][M];

        for (int n = 0; n < N; n++) {
            String[] line = reader.readLine().split("");

            for (int m = 0; m < M; m++) {
                board[n][m] = line[m].equals("W");
            }
        }

        // 결과
        int result = Integer.MAX_VALUE;

        // 0 ~ 7까지 총 8칸을 전달하므로 최대값에서 7을 뺀다.
        for (int n = 0; n < N - 7; n++) {
            for (int m = 0; m < M - 7; m++) {
                int count = solve(n, m);

                // 현재 결과보다 더 작은 수일 경우
                if (result > count) {
                    result = count;
                }
            }
        }

        writer.write(Integer.toString(result));
        writer.newLine();
        writer.close();
        reader.close();
    }

    /**
     * 새로 덧칠할 칸의 갯수 반환 함수
     *
     * @param x: [int] x의 시작좌표
     * @param y: [int] y의 시작좌표
     * @return [int] 새로 덧칠할 칸의 갯수
     */
    private static int solve(int x, int y) {
        int white = 0;
        int black = 0;

        for (int n = x; n < x + 8; n++) {
            for (int m = y; m < y + 8; m++) {
                // 하얀색으로 시작하는 체스판과 색이 다를 경우
                if (board[n][m] != WHITE[n - x][m - y]) {
                    white++;
                }

                // 검은색으로 시작하는 체스판과 색이 다를 경우
                if (board[n][m] != BLACK[n - x][m - y]) {
                    black++;
                }
            }
        }

        // 둘 중 더 적게 칠할 수 있는 체스판의 값을 반환
        return Math.min(white, black);
    }
}