알고리즘
브루트포스 (완전 탐색)
체감 난이도
★ ★ ★ ★ ☆
-> 난 완탐이 많이 약하다. 완탐+이동 조합이면 답이 없다.. 이 부분을 집중해서 풀어보자!
다시 풀 수 있는가?
YES (시간 많이 지나면 NOT SURE)
1. W 시작 체스판 & B 시작 체스판 만들어서 비교하기
뭐 하나 빠진거 찾을 때는 아예 based on 할 배열을 만들어서 비교하는 방법도 있다.
이걸 생각 못해서 어떻게 비교할지 막혔던..
String[][] wStart = {
{"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"}
};
String[][] bStart = {
{"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"}
};
2. 공백 없는 문자 split 하는 방법
이렇게 배열에 담을 수 있다.
arr[i][j] = s.split("")[j];
3. 옮기면서 비교하기
반복문 범위 설정이 어려웠던 문제이다.
// 오른쪽/아래로 옮기는 횟수
for (int i = 0; i < (N - 7); i++) {
for (int j = 0; j < (M - 7); j++) {
(N-7)을 해준건 그림으로 보자면 다음과 같다.
3번 .. 2번 .. 1번 이동을 해주기 때문에 저렇게 설정했다.
4. 안에서 비교하기
이 안에서 비교할 때는 애초에 arr[0][0] 부터 시작하는게 아니니까, i와 j를 시작점으로 뒀다.
// 그 안에서 비교
for (int k = i; k < (8 + i); k++) {
for (int l = j; l < (8 + j); l++) {
5. W로 시작하는 경우 & B로 시작하는 경우
처음에는 아예 W로 시작하는 경우 & B로 시작하는 경우를 if문으로 분리했었는데,
그렇게 하니 테케 4번이 안맞았다.
예를 들어, WWWWWWWW 이거나 BBBBBBBB 인 경우,
다시 칠하는 사람 입장이 첫 스타트를 뭐로 시작할거냐에 따라 결과가 달라진다.
그렇기 때문에 cntW와 cntB를 따로 두고, 굳이 W & B 스타트를 if문으로 분리하지 않았다.
// W로 시작하는 경우
if (!wStart[k-i][l-j].equals(arr[k][l])) {
cntW++;
}
// B로 시작하는 경우
if (!bStart[k-i][l-j].equals(arr[k][l])) {
cntB++;
}
전체 코드 ▼
더보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ1018 {
String[][] arr;
int minVal = 64;
String[][] wStart = {
{"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"}
};
String[][] bStart = {
{"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 void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
arr = new String[N][M];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
arr[i][j] = s.split("")[j];
}
}
// 오른쪽/아래로 옮기는 횟수
for (int i = 0; i < (N - 7); i++) {
for (int j = 0; j < (M - 7); j++) {
int cntW = 0;
int cntB = 0;
// 그 안에서 비교
for (int k = i; k < (8 + i); k++) {
for (int l = j; l < (8 + j); l++) {
// W로 시작하는 경우
if (!wStart[k-i][l-j].equals(arr[k][l])) {
cntW++;
}
// B로 시작하는 경우
if (!bStart[k-i][l-j].equals(arr[k][l])) {
cntB++;
}
}
}
minVal = Math.min(minVal, Math.min(cntW, cntB));
}
}
System.out.println(minVal);
}
public static void main(String[] args) throws Exception {
new BOJ1018().solution();
}
}