# 체스판 다시 칠하기 | 랭크 | 사용 언어 | | :--------------------------------------------------------: | :-----------------------------------------------------------------------------------------------------------------: | | ![image](https://d2gd6pc034wcta.cloudfront.net/tier/6.svg) | ![JAVA](https://shields.io/badge/java-JDK%2014-lightgray?logo=java&style=plastic&logoColor=white&labelColor=orange) | 🔗 [전체 1018번 문제](https://www.acmicpc.net/problem/1018) ## 조건 | 시간제한 | 메모리 제한 | | :------: | :---------: | | 2초 | 128MB | ## 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 $M \times N$ 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 $8 \times 8$ 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 $8 \times 8$ 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 $8 \times 8$ 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오. ## 입력 첫째 줄에 $N$과 $M$이 주어진다. $N$과 $M$은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 $N$개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. ## 출력 첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다. ## 케이스 ### 예제 1 + 입력 ``` tc 8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW ``` + 출력 ``` tc 1 ``` ### 예제 2 + 입력 ``` tc 10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB ``` + 출력 ``` tc 12 ``` # 풀이 각 칸이 흰색 또는 검은색으로 칠해진 커다란 판에서 임의의 위치부터 $8 \times 8$ 크기로 잘라 체스판을 만든다. 그 중 가장 적은 칸을 칠하여 체스판을 만들고자 할 때, 칠해야하는 최소값을 구하는 문제. 주어진 변수의 범위가 적어 그냥 무식하게 하나하나 비교하면 된다.

위 처럼 $N \times M$의 배열에서 무작위 $8 \times 8$ 크기의 배열을 뽑아내야한다.

$10 \times 10$짜리 배열을 기준으로, 해당 판에서 $8 \times 8$ 배열을 선택하는 경우의 수는 총 9가지이며, 이를 도식화하면 위 그림과 같다. 이처럼 전체 배열에서 $8 \times 8$만큼 한 칸씩 이동하며 비교하면 된다. ``` java for (int n = 0; n < N - 7; n++) { for (int m = 0; m < M - 7; m++) { // TODO } } ``` 위 코드와 같이 기술하면 가로부터 한 칸씩 이동하며, 끝에 도달할 경우 세로로 한 칸 이동한 뒤 다시 가로부터 한 칸씩 이동할 것이다. `n < N - 7`인 이유는 비교할 배열의 세로 길이가 8이기 때문. 살짝 헷갈린다면 `n <= N - 8`으로 대체해도 무방하다. 체스판에는 두 가지 경우의 수가 있다.

체스판의 상단 좌측을 기준으로 하얀색으로 시작하는 판과, 검은색으로 시작하는 판으로 두 가지가 존재한다. 하얀색을 `true`, 검은색을 `false`로 치환하여 하얀색 체스판과 검은색 체스판을 만들어 비교할 것이다. ``` java // 상단 좌측이 하얀색으로 시작하는 체스판 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 }, }; ``` 코드는 위와 같다. 흑백과 같이 이지선다일 경우 `boolean`을 사용하는 것을 더 선호하므로 위와 같이 설계했다. `String` 배열로 "W", "B"를 넣어 만들어도 비교만 잘 해준다면 크게 상관없다. 이를 $8 \times 8$의 모든 경우의 수와 비교하여 가장 작은 수를 출력하면 된다. ## 전체 소스 ``` java 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 1018 풀이 * @since 2021.06.26 Sat 16:46:20 */ public class Main { // 상단 좌측이 하얀색으로 시작하는 체스판 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); } } ``` 처음에 설계했을 땐, 잘라낸 $8 \times 8$ 배열 `board`의 좌측 상단값인 `board[x][y]`의 색을 찾아서, 하얀색(true)일 경우 `WHITE`를, 검은색(false)일 경우 `BLACK`을 갖고 비교했는데 계속 틀렸다. 아래 케이스를 보면 이해가 쉽다. + 입력 ``` tc 8 8 BBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW ``` + 출력 ``` 1 ``` 전체 판 자체가 $8 \times 8$이므로 경우의 수는 판 자체로 하나다. 만약 처음 설계한대로 동작한다면 위 케이스에서 문제가 발생한다. 위 케이스의 $board[0][0] = false$이므로 `BLACK`과 비교하게 된다. 이러면 $board[0][0]$를 제외한 나머지 63개의 칸을 전부 칠해야한다. 그런데 저 케이스, 자세히 한 번 보자. 사실 $board[0][0]$만 하얀색(true)로 칠해주면 그만이다. 즉, `BLACK`이 아닌 `WHITE`와 비교하면 값이 1인 것이다. ``` java /** * 새로 덧칠할 칸의 갯수 반환 함수 * * @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); } ``` `solve()` 메소드는 알고리즘의 핵심 동작이다. `WHITE`와 `BLACK`을 전부 비교하는 이유가 여기에 있는데, 현재 배열에서 `WHITE`와 `BLACK`을 만드는데 필요한 칸의 숫자를 각각 구해서, 그 중 더 작은 수를 반환해야 올바르게 동작한다. ## 분류 * 브루트포스 알고리즘

𝝅번째 알파카의 개발 낙서장

게시글

Table of Contents

😍 읽어주셔서 감사합니다!

도움이 되셨다면, .css-1stu93e{margin:0;font:inherit;color:hotpink;font-weight:700;}💝공감이나 🗨️댓글을 달아주시는 건 어떤가요?

블로그 운영에 큰 힘이 됩니다!

도움이 되셨다면, 💝공감이나 🗨️댓글을 달아주시는 건 어떤가요?