![[백준,BOJ 1018] 체스판 다시 칠하기(JAVA 구현)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FkOWy9%2FbtqzEtHgOuZ%2FNtl4I1WqkY0kLmxsciqGD1%2Fimg.png)
-내 생각
이 문제 역시 브루트 포스로 분류되어있는 문제로, 문제 자체의 이해는 완벽하다고 생각했다. 요약하자면, m*n 크기의 보드판이 있을 때, 8*8 크기의 체스판으로 뜯어 냈을 때 규칙에 맞추기 위해 칸의 색을 최소한으로 수정해야 한다는 소린데, 이 과정에서 개인적으로 간과한 부분이 바로 체스판의 (0,0)은 하얀색 또는 검은색으로 시작할 때 시작이 하얀색인 과정에서의 횟수와 검은색일 때 횟수 중 최솟값을 찾는 것이었다. 처음에 나는 보드에서 떼어낸 체스판의 시작만을 보고 규칙과 비교하여 횟수를 반환했는데, 그것이 아니라 체스판의 시작이 무엇이든 두 가지 규칙과 비교해봤어야 했다는 소리다. 말로 설명하기 굉장히 힘든데
예를들어 예제 입력 2에서 8x8의 크기로 체스판을 (0,0) ~ (10 - 8, 13-8)의 시작점을 범위로 하여 가져왔을 때 (0,0)이 B면 아래에서 Black의 규칙만을 가지고 최솟값을 찾았고, 발생할 수 있는 체스판에서 발생하는 변환 횟수 중 최솟값을 찾은 것이었다. 하지만 그것이 아니라, 발생할 수 있는 많은 체스판 각각의 black과 white의 변환 횟수 중 최솟값을 반환하고, 그렇게 반환된 최솟값을 가지고 또 다른 체스판의 최솟값과 비교해 그중에서도 최솟값을 찾는 것이 문제의 핵심이었다.(이는 8틀림의 충격으로 다른 블로그를 탐방해 알아낸 사실이다.)
더더더욱 간략히 말하자면 예제 입력 2의 경우 발생할 수 있는 체스판은 위의 범위처럼 8x8크기의 체스판을 10개 만들 수 있는데, 각 체스판에서 black과 white로 변환해보고 둘 중 최솟값을 각 체스판을 대표하는 숫자로 둔 후 10개의 체스판이 가지는 대표 숫자 중 가장 작은 값이 답인 것이다. 이 이상은 코드를 보며 설명해보자.
static final char[][] white = {
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
};
static final char[][] black = {
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
};
import java.util.*;
import java.io.*;
public class Main {
static char trans[][]; // 8x8의 체스판을 뜯어 내 저장하는 체스판 변수이다.
static char arr[][]; // nxm의 보드를 저장 할 변수이다.
static final char[][] white = { // (0,0)이 W일 때 가질 수 있는 규칙이다.
{'W','B','W','B','W','B','W','B'},
{'B','W','B','W','B','W','B','W'},
{'W','B','W','B','W','B','W','B'},
{'B','W','B','W','B','W','B','W'},
{'W','B','W','B','W','B','W','B'},
{'B','W','B','W','B','W','B','W'},
{'W','B','W','B','W','B','W','B'},
{'B','W','B','W','B','W','B','W'}
};
static final char[][] black = { // (0,0)이 B일 때 가질 수 있는 규칙이다.
{'B','W','B','W','B','W','B','W'},
{'W','B','W','B','W','B','W','B'},
{'B','W','B','W','B','W','B','W'},
{'W','B','W','B','W','B','W','B'},
{'B','W','B','W','B','W','B','W'},
{'W','B','W','B','W','B','W','B'},
{'B','W','B','W','B','W','B','W'},
{'W','B','W','B','W','B','W','B'}
};
public static int trans(int a, int b,int min) { // 뜯어낸 체스판을 각 규칙과 비교하는 메소드
int cnt_b =0; // BLACK 규칙과 비교하여 발생하는 변환횟수 저장 변수
int cnt_w =0; // WHITE "
int k=0;
StringBuilder builder = new StringBuilder("");
for(int i =a;i<a+8;i++) { // 시작점이 전달되면 그로부터 8칸을 보드에서 가져온다
builder.setLength(0); //StringBuilder 초기화 , 공백으로 만든다.
for(int j=b;j<b+8;j++) { // 시작점이 전달되면 그로부터 8칸을 보드에서 가져온다
builder.append(arr[i][j]); // 보드에서 가져온 해당 점을 stringbuilder에 저장
}
for(int j=0;j<builder.length();j++) {
trans[k][j] = builder.charAt(j); //행 단위로 체스판 배열에 저장
}
k++; // 체스판 행 증가,
}
for(int i=0;i<trans.length;i++) { // 체스판을 탐색
for(int j=0;j<trans[i].length;j++) {
if(trans[i][j]!=black[i][j]) { // black의 규칙으로 변환되는 횟수
cnt_b++;
}
if(trans[i][j]!=white[i][j]) { // white의 규칙으로 변환되는 횟수
cnt_w++;
}
}
}
return Math.min(Math.min(cnt_w, cnt_b), min); // min값은 다른 체스판에서 발생한 최솟값
// 첫 번째 인자는 현재 체스판에서 black과 white의 변환횟수 중 최솟값
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Input
int n = sc.nextInt();
int m = sc.nextInt();
arr = new char [n][m];
trans = new char [8][8];
for(int i=0;i<n;i++) { // 행 단위로 입력
String row = sc.next();
for(int j=0;j<m;j++) {
arr[i][j] = row.charAt(j);
}
}
int min = Integer.MAX_VALUE;
for(int i=0;i<=n-8;i++) {// (0,0) ~ (n-8, m-8)의 범위만큼 시작점을 전달
for(int j=0;j<=m-8;j++) {
min =trans(i,j,min); // 위의 메소드로 시작점과 현재까지 만든 체스판 중 최솟값 전달
}
}
System.out.println(min);//output
}
}
알고리즘 초보자 입장으로써 다른 블로그에 잘 설명되어있는 글들에 항상 감사하고 있는데, 그 수가 적어 찾는데 어려움을 많이 느낀다. 그렇기 때문에 나는 최대한 상세히 작성하고자 하는데 말처럼 쉬운 게 아닌 것 같다...
(체스판의 칸 하나 하나를 모든 규칙에 비교한다는 점에서 브루트 포스 알고리즘 다운 문제였다.)