[Java] 백준(실버-4) 1018번 - 체스판 다시 칠하기
자세한 테스트케이스 데이터는 문제링크를 참고하자.
문제 풀이
이 문제는 이해하는 것부터 어려움이 있었다.
8X8 크기의 정사각형을 아무데서나 골라서 가장 적게 칠해야할 횟수를 구해야 하는데 잘 생각해보니 결국 NXM 크기의 정사각형에서 8X8 크기의 정삭각형 범위만큼 탐색해야 했다.
모든 8X8 정사각형을 탐색하면서 블랙체스판일 때 칠해야할 횟수와 화이트체스판일 때 칠해야할 횟수를 비교하여 더 적은 횟수를 구하면 된다.
아이디어 도출
- 주어진 NXM 크기의 정사각형을 2차원 배열에 담는다.
- NXM 크기의 정사각형에서 8X8 정사각형 범위만큼 순회한다.
- 8X8 정사각형에서 블랙체스판, 화이트체스판 2가지 경우일 때 칠해야 할 횟수를 비교하여 더 적은 횟수를 구한다.
- 8X8 정사각형에서 (0,0) 값이 “B”이면 블랙체스판, “W”라면 화이트체스판으로 간주하자.
- 블랙 체스판 일 경우 짝수행(0,2,4,6)이 “BWBWBWBW”이고, 홀수행(1,3,5,7)이 “WBWBWBWB”이어야 한다.
- 주어진 행 값과 블랙체스판이 되어야 할 문자열 “BWBWBWBW”을 비교하여 다른 문자열이 있다면 칠해야할 횟수를 1 증가시킨다.
- 화이트 체스판 일 경우 짝수행(0,2,4,6)이 “WBWBWBWB”이고, 홀수행(1,3,5,7)이 “BWBWBWBW”이어야 한다.
- 주어진 행 값과 화이트체스판이 되어야 할 문자열 “WBWBWBWB”을 비교하여 다른 문자열이 있다면 칠해야할 횟수를 1 증가시킨다.
- 블랙체스판이나 화이트체스판일 경우의 칠해야할 횟수 중 더 작은 값으로 반환한다.
- NXM 크기의 정사각형에서 8X8 크기의 정사각형만큼 돌면서 가장 최소값으로 칠해야 할 횟수를 구한다.
겉으로 보기엔 복잡해보이지만 아이디어는 단순하다.
말 그대로 NXM 크기의 2차원 배열에서 8X8 크기만큼 순회하는데,
여기서 핵심은 8X8 정사각형에서 블랙체스판, 화이트체스판 2가지 경우의 수를 비교하는 것이다.
그래서 결국 8X8 정사각형에서 칠해야할 횟수를 구해가며 더 적게 칠해야할 횟수를 구할 수 있게 된다.
이제 코드를 작성해보자.
1
2
3
4
5
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String[][] arr = new String[N][M];
먼저 N과 M을 입력받고, 2차원 String 배열 arr를 NXM 크기로 선언하자.
1
2
3
4
for(int i=0; i<N; i++) {
String[] strs = br.readLine().split("");
arr[i] = strs;
}
그리고 arr에 입력받은 NXM 크기의 정사각형 원소들을 저장한다.
1
2
3
4
5
6
int cnt = getMinCnt(arr, 0, 0);
for(int i=0; i<arr.length-7; i++) {
for(int j=0; j<arr[i].length-7; j++) {
cnt = Math.min(cnt, getMinCnt(arr, i, j));
}
}
NXM 크기의 정사각형에서 8X8 크기의 정사각형만큼 돌면서 각 8X8 정사각형마다의 칠해야 할 횟수를 getMinCnt() 함수를 통해 구하여 cnt에 저장해나간다.
8X8 정사각형마다 구해진 칠해야할 횟수가 더 적은 횟수로 cnt를 최신화하면 NXM 정사각형에서 다시 칠해야할 최소 횟수를 구할 수 있다.
이중 for문을 돌며 NXM 정사각형에서 8X8 크기의 정사각형만큼 순회하기 위해 i와 j는 8만큼 반복한다.
이제 8X8 정사각형에서 다시 칠해야할 최소 횟수를 구하는 getMinCnt() 함수를 살펴보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public static int getMinCnt(String[][] arr, int start_x, int start_y) {
String[] chess = {"BWBWBWBW","WBWBWBWB"};
int end_x = start_x+8;
int end_y = start_y+8;
int cnt = 0;
boolean BW = true;
if(arr[start_x][start_y].equals("W")) BW = false;
else BW = true;
for(int i=start_x; i<end_x; i++) {
String row = "";
for(int j=start_y; j<end_y; j++) {
row += arr[i][j];
}
/* 8X8 사각형의 (0,0) 값이 B, 블랙 체스판 일 경우
* 0,2,4,6 행이 BWBWBWBW 이어야 함.
* 1,3,5,7 행이 WBWBWBWB 이어야 함.
*
*/
if(BW) {
if(i%2 == 0) {
if(!row.equals(chess[0])) {
for(int k=0; k<row.length(); k++) {
if(row.charAt(k) != chess[0].charAt(k)) cnt++;
}
}
}
else if(i%2 == 1) {
if(!row.equals(chess[1])) {
for(int k=0; k<row.length(); k++) {
if(row.charAt(k) != chess[1].charAt(k)) cnt++;
}
}
}
}
/* 8X8 사각형의 (0,0) 값이 W, 화이트 체스판 일 경우
* 0,2,4,6 행이 WBWBWBWB 이어야 함.
* 1,3,5,7 행이 BWBWBWBW 이어야 함.
*
*/
else if(!BW) {
if(i%2 == 0) {
if(!row.equals(chess[1])) {
for(int k=0; k<row.length(); k++) {
if(row.charAt(k) != chess[1].charAt(k)) cnt++;
}
}
}
else if(i%2 == 1) {
if(!row.equals(chess[0])) {
for(int k=0; k<row.length(); k++) {
if(row.charAt(k) != chess[0].charAt(k)) cnt++;
}
}
}
}
}
// 블랙체스판 이라면 칠해야할 횟수와 화이트체스판의 칠해야할 횟수(64 - 블랙체스판 횟수)를 비교하여 적은 값을 반환한다.
// 반대로 화이트체스판 이라면 칠해야할 횟수와 블랙체스판의 칠해야할 횟수(64 - 화이트체스판 횟수)를 비교하여 적은 값을 반환한다.
return Math.min(cnt, 64-cnt);
}
이 함수의 내용이 가장 중요하다고 본다. 순서대로 무슨 코드인지 살펴보자.
-
먼저 8X8 정사각형에서 (0,0) 값을 통해 블랙체스판인지 화이트체스판인지를 구분한다.
-
그리고 NXM에서 인덱스를 하나씩 옮겨가며 8X8 정사각형들을 탐색해야하기 때문에 (0~7,0~7), (0~7, 1~8), (0~7, 2~9) … 등의 인덱스로 접근해야 한다.
main 메서드에서 getMinCnt() 함수의 인자로 넘겨준 i와 j 값부터 각각 8씩 증가시켜 탐색하여 8X8 정사각형들을 찾을 수 있다. -
만약 현재 탐색된 8X8 정사각형이 블랙 체스판이라면 짝수행이 “BWBWBWBW”인지 검증하고, 홀수행이 “WBWBWBWB”인지 검증한다.
반대로 화이트체스판이라면 짝수행이 “WBWBWBWB”인지 검증하고, 홀수행이 “BWBWBWBW”인지 검증한다.
위 2가지 비교검증을 통해서 다른 문자열이 있다면 칠해야할 횟수를 1 증가시킨다. -
마지막으로 각 8X8 정사각형에서 체스판 여부와 칠해야할 횟수를 구했으니, 반대되는 체스판 칠해야할 횟수와 비교하여 더 적게 칠해야할 횟수를 반환하면 된다.
예를 들어 현재 탐색된 정사각형이 블랙체스판이고 12번의 칠해야할 횟수를 구했다면, 화이트체스판일 때는 52(64-12)번만큼 칠해야 하기 때문에 블랙체스판 일때의 칠해야할 횟수 12번을 반환하면 되는 것이다.
자 다시, main 메서드로 돌아와 코드를 살펴보면
1
2
3
4
5
6
7
int cnt = getMinCnt(arr, 0, 0);
for(int i=0; i<arr.length-7; i++) {
for(int j=0; j<arr[i].length-7; j++) {
cnt = Math.min(cnt, getMinCnt(arr, i, j));
}
}
bw.write(cnt+"\n");
cnt 변수에 getMinCnt() 함수를 통해 8X8 정사각형마다의 최소 칠할 횟수를 받아온다.
여기서도 마찬가지로 cnt가 가장 최소로 칠할 횟수로 최신화 되어야 하기에 최소가 되는 횟수를 cnt에 저장해나가면 된다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String[][] arr = new String[N][M];
for(int i=0; i<N; i++) {
String[] strs = br.readLine().split("");
arr[i] = strs;
}
int cnt = getMinCnt(arr, 0, 0);
for(int i=0; i<arr.length-7; i++) {
for(int j=0; j<arr[i].length-7; j++) {
cnt = Math.min(cnt, getMinCnt(arr, i, j));
}
}
bw.write(cnt+"\n");
bw.flush();
bw.close();
br.close();
}
public static int getMinCnt(String[][] arr, int start_x, int start_y) {
String[] chess = {"BWBWBWBW","WBWBWBWB"};
int end_x = start_x+8;
int end_y = start_y+8;
int cnt = 0;
boolean BW = true;
if(arr[start_x][start_y].equals("W")) BW = false;
else BW = true;
for(int i=start_x; i<end_x; i++) {
String row = "";
for(int j=start_y; j<end_y; j++) {
row += arr[i][j];
}
/* 8X8 사각형의 (0,0) 값이 B, 블랙 체스판 일 경우
* 0,2,4,6 행이 BWBWBWBW 이어야 함.
* 1,3,5,7 행이 WBWBWBWB 이어야 함.
*
*/
if(BW) {
if(i%2 == 0) {
if(!row.equals(chess[0])) {
for(int k=0; k<row.length(); k++) {
if(row.charAt(k) != chess[0].charAt(k)) cnt++;
}
}
}
else if(i%2 == 1) {
if(!row.equals(chess[1])) {
for(int k=0; k<row.length(); k++) {
if(row.charAt(k) != chess[1].charAt(k)) cnt++;
}
}
}
}
/* 8X8 사각형의 (0,0) 값이 W, 화이트 체스판 일 경우
* 0,2,4,6 행이 WBWBWBWB 이어야 함.
* 1,3,5,7 행이 BWBWBWBW 이어야 함.
*
*/
else if(!BW) {
if(i%2 == 0) {
if(!row.equals(chess[1])) {
for(int k=0; k<row.length(); k++) {
if(row.charAt(k) != chess[1].charAt(k)) cnt++;
}
}
}
else if(i%2 == 1) {
if(!row.equals(chess[0])) {
for(int k=0; k<row.length(); k++) {
if(row.charAt(k) != chess[0].charAt(k)) cnt++;
}
}
}
}
}
return Math.min(cnt, 64-cnt);
}
}
회고
- 문제를 풀기 위한 아이디어는 생각해냈지만, 2차원 배열을 통해서 생각한대로 구현하는게 만만치 않았다. 2차원 배열을 활용해 특정 인덱스별로 바뀌며 탐색해야 하는 방식을 더 공부하고 2차원 배열 관련 문제를 더 풀어야겠다.
- 다른 분들의 풀이를 살펴보니, boolean 2차원 배열을 활용하여 푼 방식이 있었는데, 짝수행, 홀수행을 구분짓지 않고도 풀 수 있음에 감탄하였다. st님의 풀이를 나중에 꼭 참고하여 다시 풀어보자.