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

screen

[백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기

posts

알고리즘

시리즈 톺아보기

백준 알고리즘

백준 알고리즘
count

체스판 다시 칠하기 🔗

랭크 사용 언어
image JAVA

🔗 전체 1018번 문제

조건 🔗

시간제한 메모리 제한
2초 128MB

문제 🔗

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

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

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

입력 🔗

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

출력 🔗

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

케이스 🔗

예제 1 🔗

  • 입력

TC

08 8
1WBWBWBWB
2BWBWBWBW
3WBWBWBWB
4BWBBBWBW
5WBWBWBWB
6BWBWBWBW
7WBWBWBWB
8BWBWBWBW
  • 출력

TC

01

예제 2 🔗

  • 입력

TC

010 13
1BBBBBBBBWBWBW
2BBBBBBBBBWBWB
3BBBBBBBBWBWBW
4BBBBBBBBBWBWB
5BBBBBBBBWBWBW
6BBBBBBBBBWBWB
7BBBBBBBBWBWBW
8BBBBBBBBBWBWB
9WWWWWWWWWWBWB
10WWWWWWWWWWBWB
  • 출력

TC

012

풀이 🔗

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

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

짜리 배열을 기준으로, 해당 판에서 배열을 선택하는 경우의 수는 총 9가지이며, 이를 도식화하면 위 그림과 같다. 이처럼 전체 배열에서 만큼 한 칸씩 이동하며 비교하면 된다.

JAVA

0for (int n = 0; n < N - 7; n++)
1{
2 for (int m = 0; m < M - 7; m++)
3 {
4 // TODO
5 }
6}

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

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

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

JAVA

0// 상단 좌측이 하얀색으로 시작하는 체스판
1private static final boolean[][] WHITE = {
2 { true, false, true, false, true, false, true, false },
3 { false, true, false, true, false, true, false, true },
4 { true, false, true, false, true, false, true, false },
5 { false, true, false, true, false, true, false, true },
6 { true, false, true, false, true, false, true, false },
7 { false, true, false, true, false, true, false, true },
8 { true, false, true, false, true, false, true, false },
9 { false, true, false, true, false, true, false, true },
10};
11
12// 상단 좌측이 검은색으로 시작하는 체스판
13private static final boolean[][] BLACK = {
14 { false, true, false, true, false, true, false, true },
15 { true, false, true, false, true, false, true, false },
16 { false, true, false, true, false, true, false, true },
17 { true, false, true, false, true, false, true, false },
18 { false, true, false, true, false, true, false, true },
19 { true, false, true, false, true, false, true, false },
20 { false, true, false, true, false, true, false, true },
21 { true, false, true, false, true, false, true, false },
22};

코드는 위와 같다. 흑백과 같이 이지선다일 경우 boolean을 사용하는 것을 더 선호하므로 위와 같이 설계했다. String 배열로 "W", "B"를 넣어 만들어도 비교만 잘 해준다면 크게 상관없다. 이를 의 모든 경우의 수와 비교하여 가장 작은 수를 출력하면 된다.

전체 소스 🔗

JAVA

0import java.io.BufferedReader;
1import java.io.BufferedWriter;
2import java.io.IOException;
3import java.io.InputStreamReader;
4import java.io.OutputStreamWriter;
5import java.util.Arrays;
6
7/**
8 * 백준 전체 1018 문제 알고리즘 클래스
9 *
10 * @author RWB
11 * @see <a href="https://blog.itcode.dev/posts/2021/06/26/a1018">1018 풀이</a>
12 * @since 2021.06.26 Sat 16:46:20
13 */
14public class Main
15{
16 // 상단 좌측이 하얀색으로 시작하는 체스판
17 private static final boolean[][] WHITE = {
18 { true, false, true, false, true, false, true, false },
19 { false, true, false, true, false, true, false, true },
20 { true, false, true, false, true, false, true, false },
21 { false, true, false, true, false, true, false, true },
22 { true, false, true, false, true, false, true, false },
23 { false, true, false, true, false, true, false, true },
24 { true, false, true, false, true, false, true, false },
25 { false, true, false, true, false, true, false, true },
26 };
27
28 // 상단 좌측이 검은색으로 시작하는 체스판
29 private static final boolean[][] BLACK = {
30 { false, true, false, true, false, true, false, true },
31 { true, false, true, false, true, false, true, false },
32 { false, true, false, true, false, true, false, true },
33 { true, false, true, false, true, false, true, false },
34 { false, true, false, true, false, true, false, true },
35 { true, false, true, false, true, false, true, false },
36 { false, true, false, true, false, true, false, true },
37 { true, false, true, false, true, false, true, false },
38 };
39
40 // 체스판
41 private static boolean[][] board;
42
43 /**
44 * 메인 함수
45 *
46 * @param args: [String[]] 매개변수
47 *
48 * @throws IOException 데이터 입출력 예외
49 */
50 public static void main(String[] args) throws IOException
51 {
52 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
53 BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
54
55 int[] temp = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
56
57 // 세로 길이
58 int N = temp[0];
59
60 // 가로 길이
61 int M = temp[1];
62
63 board = new boolean[N][M];
64
65 for (int n = 0; n < N; n++)
66 {
67 String[] line = reader.readLine().split("");
68
69 for (int m = 0; m < M; m++)
70 {
71 board[n][m] = line[m].equals("W");
72 }
73 }
74
75 // 결과
76 int result = Integer.MAX_VALUE;
77
78 // 0 ~ 7까지 총 8칸을 전달하므로 최대값에서 7을 뺀다.
79 for (int n = 0; n < N - 7; n++)
80 {
81 for (int m = 0; m < M - 7; m++)
82 {
83 int count = solve(n, m);
84
85 // 현재 결과보다 더 작은 수일 경우
86 if (result > count)
87 {
88 result = count;
89 }
90 }
91 }
92
93 writer.write(Integer.toString(result));
94 writer.newLine();
95 writer.close();
96 reader.close();
97 }
98
99 /**
100 * 새로 덧칠할 칸의 갯수 반환 함수
101 *
102 * @param x: [int] x의 시작좌표
103 * @param y: [int] y의 시작좌표
104 *
105 * @return [int] 새로 덧칠할 칸의 갯수
106 */
107 private static int solve(int x, int y)
108 {
109 int white = 0;
110 int black = 0;
111
112 for (int n = x; n < x + 8; n++)
113 {
114 for (int m = y; m < y + 8; m++)
115 {
116 // 하얀색으로 시작하는 체스판과 색이 다를 경우
117 if (board[n][m] != WHITE[n - x][m - y])
118 {
119 white++;
120 }
121
122 // 검은색으로 시작하는 체스판과 색이 다를 경우
123 if (board[n][m] != BLACK[n - x][m - y])
124 {
125 black++;
126 }
127 }
128 }
129
130 // 둘 중 더 적게 칠할 수 있는 체스판의 값을 반환
131 return Math.min(white, black);
132 }
133}

처음에 설계했을 땐, 잘라낸 배열 board의 좌측 상단값인 board[x][y]의 색을 찾아서, 하얀색(true)일 경우 WHITE를, 검은색(false)일 경우 BLACK을 갖고 비교했는데 계속 틀렸다. 아래 케이스를 보면 이해가 쉽다.

  • 입력

TC

08 8
1BBWBWBWB
2BWBWBWBW
3WBWBWBWB
4BWBWBWBW
5WBWBWBWB
6BWBWBWBW
7WBWBWBWB
8BWBWBWBW
  • 출력

전체 판 자체가 이므로 경우의 수는 판 자체로 하나다. 만약 처음 설계한대로 동작한다면 위 케이스에서 문제가 발생한다.

위 케이스의 이므로 BLACK과 비교하게 된다. 이러면 를 제외한 나머지 63개의 칸을 전부 칠해야한다. 그런데 저 케이스, 자세히 한 번 보자. 사실 만 하얀색(true)로 칠해주면 그만이다. 즉, BLACK이 아닌 WHITE와 비교하면 값이 1인 것이다.

JAVA

0/**
1 * 새로 덧칠할 칸의 갯수 반환 함수
2 *
3 * @param x: [int] x의 시작좌표
4 * @param y: [int] y의 시작좌표
5 *
6 * @return [int] 새로 덧칠할 칸의 갯수
7 */
8private static int solve(int x, int y)
9{
10 int white = 0;
11 int black = 0;
12
13 for (int n = x; n < x + 8; n++)
14 {
15 for (int m = y; m < y + 8; m++)
16 {
17 // 하얀색으로 시작하는 체스판과 색이 다를 경우
18 if (board[n][m] != WHITE[n - x][m - y])
19 {
20 white++;
21 }
22
23 // 검은색으로 시작하는 체스판과 색이 다를 경우
24 if (board[n][m] != BLACK[n - x][m - y])
25 {
26 black++;
27 }
28 }
29 }
30
31 // 둘 중 더 적게 칠할 수 있는 체스판의 값을 반환
32 return Math.min(white, black);
33}

solve() 메소드는 알고리즘의 핵심 동작이다. WHITEBLACK을 전부 비교하는 이유가 여기에 있는데, 현재 배열에서 WHITEBLACK을 만드는데 필요한 칸의 숫자를 각각 구해서, 그 중 더 작은 수를 반환해야 올바르게 동작한다.

분류 🔗

  • 브루트포스 알고리즘