- [백준 / JAVA] 백준 알고리즘 1021번 회전하는 큐
- [백준 / JAVA] 백준 알고리즘 1020번 디지털 카운터
- [백준 / JAVA] 백준 알고리즘 1019번 책 페이지
👀 [백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기
- [백준 / JAVA] 백준 알고리즘 1017번 소수 쌍
- [백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수
- [백준 / JAVA] 백준 알고리즘 1015번 수열 정렬
- [백준 / JAVA] 백준 알고리즘 1014번 컨닝
- [백준 / JAVA] 백준 알고리즘 1013번 Contact
- [백준 / JAVA] 백준 알고리즘 1012번 유기농 배추
- [백준 / JAVA] 백준 알고리즘 1011번 Fly me to the Alpha Centauri
- [백준 / JAVA] 백준 알고리즘 1010번 다리 놓기
- [백준 / JAVA] 백준 알고리즘 1009번 분산처리
- [백준 / JAVA] 백준 알고리즘 1008번 A / B
- [백준 / JAVA] 백준 알고리즘 1007번 벡터
- [백준 / JAVA] 백준 알고리즘 1006번 습격자 초라기
- [백준 / JAVA] 백준 알고리즘 1005번 ACM Craft
- [백준 / JAVA] 백준 알고리즘 1004번 어린 왕자
- [백준 / JAVA] 백준 알고리즘 1003번 피보나치 함수
- [백준 / JAVA] 백준 알고리즘 1002번 터렛
- [백준 / JAVA] 백준 알고리즘 1001번 A - B
- [백준 / JAVA] 백준 알고리즘 1000번 A + B
- 백준 알고리즘 시작하기
체스판 다시 칠하기 🔗
조건 🔗
시간제한 | 메모리 제한 |
---|---|
2초 | 128MB |
문제 🔗
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력 🔗
첫째 줄에 과 이 주어진다. 과 은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력 🔗
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
케이스 🔗
예제 1 🔗
- 입력
TC
0 | 8 8 |
1 | WBWBWBWB |
2 | BWBWBWBW |
3 | WBWBWBWB |
4 | BWBBBWBW |
5 | WBWBWBWB |
6 | BWBWBWBW |
7 | WBWBWBWB |
8 | BWBWBWBW |
- 출력
TC
0 | 1 |
예제 2 🔗
- 입력
TC
0 | 10 13 |
1 | BBBBBBBBWBWBW |
2 | BBBBBBBBBWBWB |
3 | BBBBBBBBWBWBW |
4 | BBBBBBBBBWBWB |
5 | BBBBBBBBWBWBW |
6 | BBBBBBBBBWBWB |
7 | BBBBBBBBWBWBW |
8 | BBBBBBBBBWBWB |
9 | WWWWWWWWWWBWB |
10 | WWWWWWWWWWBWB |
- 출력
TC
0 | 12 |
풀이 🔗
각 칸이 흰색 또는 검은색으로 칠해진 커다란 판에서 임의의 위치부터 크기로 잘라 체스판을 만든다. 그 중 가장 적은 칸을 칠하여 체스판을 만들고자 할 때, 칠해야하는 최소값을 구하는 문제. 주어진 변수의 범위가 적어 그냥 무식하게 하나하나 비교하면 된다.
위 처럼 의 배열에서 무작위 크기의 배열을 뽑아내야한다.
짜리 배열을 기준으로, 해당 판에서 배열을 선택하는 경우의 수는 총 9가지이며, 이를 도식화하면 위 그림과 같다. 이처럼 전체 배열에서 만큼 한 칸씩 이동하며 비교하면 된다.
JAVA
0 | for (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 | // 상단 좌측이 하얀색으로 시작하는 체스판 |
1 | private 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 | // 상단 좌측이 검은색으로 시작하는 체스판 |
13 | private 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
0 | import java.io.BufferedReader; |
1 | import java.io.BufferedWriter; |
2 | import java.io.IOException; |
3 | import java.io.InputStreamReader; |
4 | import java.io.OutputStreamWriter; |
5 | import 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 | */ |
14 | public 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
0 | 8 8 |
1 | BBWBWBWB |
2 | BWBWBWBW |
3 | WBWBWBWB |
4 | BWBWBWBW |
5 | WBWBWBWB |
6 | BWBWBWBW |
7 | WBWBWBWB |
8 | BWBWBWBW |
- 출력
전체 판 자체가 이므로 경우의 수는 판 자체로 하나다. 만약 처음 설계한대로 동작한다면 위 케이스에서 문제가 발생한다.
위 케이스의 이므로 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 | */ |
8 | private 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()
메소드는 알고리즘의 핵심 동작이다. WHITE
와 BLACK
을 전부 비교하는 이유가 여기에 있는데, 현재 배열에서 WHITE
와 BLACK
을 만드는데 필요한 칸의 숫자를 각각 구해서, 그 중 더 작은 수를 반환해야 올바르게 동작한다.
분류 🔗
- 브루트포스 알고리즘
📆 작성일
2021-06-26 Sat 16:46:20
📚 카테고리
🏷️ 태그