[백준] 1018번:체스판 다시 칠하기 자바 (Java)
문제
접근법
이 문제의 핵심은 총 2가지이다.
1. 기본적으로, 브루트포스 알고리즘이기 때문에 처음부터 끝까지 모두 탐색할 생각으로 접근해야 한다.
2. 8x8 정사각형의 첫 번째 block은 검은색일 수도 하얀색일 수도 있다.
3. 전체 보드가 NxM 크기라고 할때, 그곳에 들어가는 체스판의 개수는 (N-7) x(M-7)이다.
-> 이는 체스판의 좌상단의 사각형의 위치를 잘 생각해보면 쉽게 계산이 가능하다.
풀이
내가 첫번째로 작성한 풀이는 다음과 같다. 체스판의 좌상단이 검은색이냐 하얀색이냐로 경우를 나누고 좌상단의 사각형을 기준으로 8x8 정사각형을 모두 알파벳을 비교하여 수를 세주었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] size = br.readLine().split(" ");
int row_size = Integer.parseInt(size[0]);
int col_size = Integer.parseInt(size[1]);
String[] line = new String[row_size];
for (int i = 0; i < row_size; i++) {
line[i] = br.readLine();
}
int min = Integer.MAX_VALUE; //칠하는 최소 정사각형
final int LIMIT = 8;
boolean isBlack = true; //조회하는 정사각형의 첫번째 칸을 검정색이라고 가정
int flag = 0;
while (isBlack || flag ==1) {
flag++;
for (int start_row = 0; start_row < row_size - 7; start_row++) {
for (int start_col = 0; start_col < col_size - 7; start_col++) {
int temp = getMin(start_row, start_col, line, isBlack);
if (temp < min) {
min = temp;
}
}
}
isBlack = false;
}
System.out.println(min);
}
private static int getMin(int start_row, int start_col, String[] line, boolean isBlack) {
final String WHITE = "WBWBWBWB";
final String BLACK = "BWBWBWBW";
int count = 0;
for (int i = 0; i < 8; i++) { //8x8 정사각형 조회
String check = line[start_row+i].substring(start_col, start_col +8);
for (int j = 0; j < 8; j++) {
count = getCount(isBlack, i, count, BLACK, j, check, WHITE);
}
}
return count;
}
private static int getCount(boolean isBlack, int i, int count, String BLACK, int j, String check, String WHITE) {
if (i % 2 == 0) {
if (isBlack) {
count = compareLine(BLACK, j, check, count);
} else {
count = compareLine(WHITE, j, check, count);
}
} else {
if (isBlack) {
count = compareLine(WHITE, j, check, count);
} else {
count = compareLine(BLACK, j, check, count);
}
}
return count;
}
private static int compareLine(String s, int j, String check, int count) {
if (s.charAt(j) != check.charAt(j)) {
count++;
}
return count;
}
}
코드가 너무 복잡하여 이를 개선할 수 있는 방향을 두가지 생각해 보았다.
1. 체스판의 좌상단의 색이 검은색이냐 하얀색이냐를 꼭 나눠야 할까?
우선, 체스판의 좌상단이 검은색이냐 하얀색이냐의 경우를 나누는 것은 사실상 무의미하다. 체스판의 좌상단을 검은색이라고 가정했을 때, 문자열을 모두 비교한 값과 체스판의 좌상단을 하얀색이라고 가정했을 때, 문자열을 모두 비교한 값의 합은 64(8x8)이기 때문이다.
이유는 다음과 같다. 검정색이라고 가정했을 경우 다시 칠하는 정사각형의 개수는 결국 하얀색이라고 가정했을 경우 체스판과 일치하다고 판단되는 단위 정사각형이기 때문이다. (말을 좀 어렵게 풀긴 했지만, 곰곰이 생각해 보면 답이 나올 것이다.)
코드로 확실히 이해해 보자.
int min = 64; //칠하는 최소 정사각형
for (int start_row = 0; start_row < row_size - 7; start_row++) {
for (int start_col = 0; start_col < col_size - 7; start_col++) {
int temp = getMin(start_row, start_col, line);
min = Math.min(temp, min);
}
}
System.out.println(min);
}
private static int getMin(int start_row, int start_col, String[] line) {
final String WHITE = "WBWBWBWB";
final String BLACK = "BWBWBWBW";
int count = 0;
for (int i = 0; i < 8; i++) { //8x8 정사각형 조회
String check = line[start_row+i].substring(start_col, start_col +8);
for (int j = 0; j < 8; j++) {
count = getCount(i, count, BLACK, j, check, WHITE);
}
}
count = Math.min(count, 64 - count);
return count;
}
private static int getCount(int i, int count, String BLACK, int j, String check, String WHITE) {
if (i % 2 == 0) {
count = compareLine(WHITE, j, check, count);
} else {
count = compareLine(BLACK, j, check, count);
}
return count;
}
private static int compareLine(String s, int j, String check, int count) {
if (s.charAt(j) != check.charAt(j)) {
count++;
}
return count;
}
Math.min(count, 64 - count) 한 줄로 두 가지 경우를 한 번에 처리해 주는 것을 확인할 수 있다.
2. min의 최댓값은 몇일까?
현재, min은 내가 찾은 값들 중 가장 작은 값을 넣어야 하기 때문에, 아래와 같이 min을 정수형이 갖는 최대 값을 선언하여 갱신해주고 있는 형태이다.
int min = Integer.MAX_VALUE; //칠하는 최소 정사각형
for (int start_row = 0; start_row < row_size - 7; start_row++) {
for (int start_col = 0; start_col < col_size - 7; start_col++) {
int temp = getMin(start_row, start_col, line);
if (temp < min) {
min = temp;
}
}
}
이 방법도 틀린 것은 아니지만, 메모리가 낭비된다는 문제가 있다. 곰곰이 생각해 보면, 8x8 체스판 위에서 min이 가질 수 있는 최댓값은 당연히 64이다. 따라서, 다음과 같이 바꾸면 깔끔하게 코드가 작성된다.
int min = 64; //칠하는 최소 정사각형
for (int start_row = 0; start_row < row_size - 7; start_row++) {
for (int start_col = 0; start_col < col_size - 7; start_col++) {
int temp = getMin(start_row, start_col, line);
min = Math.min(temp, min);
}
}
전체코드는 다음과 같으니 참고 바란다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] size = br.readLine().split(" ");
int row_size = Integer.parseInt(size[0]);
int col_size = Integer.parseInt(size[1]);
String[] line = new String[row_size];
for (int i = 0; i < row_size; i++) {
line[i] = br.readLine();
}
int min = 64; //칠하는 최소 정사각형
for (int start_row = 0; start_row < row_size - 7; start_row++) {
for (int start_col = 0; start_col < col_size - 7; start_col++) {
int temp = getMin(start_row, start_col, line);
min = Math.min(temp, min);
}
}
System.out.println(min);
}
private static int getMin(int start_row, int start_col, String[] line) {
final String WHITE = "WBWBWBWB";
final String BLACK = "BWBWBWBW";
int count = 0;
for (int i = 0; i < 8; i++) { //8x8 정사각형 조회
String check = line[start_row+i].substring(start_col, start_col +8);
for (int j = 0; j < 8; j++) {
count = getCount(i, count, BLACK, j, check, WHITE);
}
}
count = Math.min(count, 64 - count);
return count;
}
private static int getCount(int i, int count, String BLACK, int j, String check, String WHITE) {
if (i % 2 == 0) {
count = compareLine(WHITE, j, check, count);
} else {
count = compareLine(BLACK, j, check, count);
}
return count;
}
private static int compareLine(String s, int j, String check, int count) {
if (s.charAt(j) != check.charAt(j)) {
count++;
}
return count;
}
}
정리
거의 일일이 탐색해 주면 되기 때문에 그리 어렵진 않은 문제였다. 8x8 체스판 위에서 정사각형의 개수를 찾는 것이라고 범위를 한정해서 생각하면 더욱 쉽게 풀 수 있었던 문제인 것 같다.