문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8×8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
예제 입력
10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB
예제 출력
12
내가 했던 풀이 방법
- Wdot와 Bdot Set를 만들고, board판을 모두 확인해준다. (0,0)이 흰색일 때, 검은색일 때를 나누어서 잘못 그려진 위치를 문자열 형태로 Wdot와 Bdot에 넣어준다. (Wdot은 시작이 W이면서 잘못된 좌표의 Set이다.) 예를 들어 시작색을 흰색으로 둘 때, (0,1)은 검은색이어야 하지만, W일 때 Wdot에 "0,1"을 넣어준다. 문자열 형태로 넣어주는 이유는 [0, 1]로 넣어주게 되면 이후 has를 사용할 수 없기 때문에 문자열 형태로 저장해준다. -> Set은 내부 요소의 동등성을 판단할 때 배열의 참조를 기준으로 하기 때문에, 동일한 배열 내용이라 할지라도 다른 참조를 갖는 경우 다른 요소로 인식된다.
- 8×8 크기로 잘라주어야 하기 때문에 for문에서 N/M까지 돌 필요가 없다. N-8/M-8까지만 확인해도 된다. board판 위치를 바꿔줄 때마다 각 count 변수를 0으로 초기화해준다.
- 현재 위치를 시작점으로 해서 8×8 board판이 감싸는 모든 위치를 검사하면서, 각 dot 배열에 해당 좌표가 있는지 검사해준다. 해당 좌표가 있을 경우, 각 count를 1씩 증가시켜준다.
- 모든 위치를 검사했다면, 각 min값과 count를 비교해서 count가 더 작을 경우, min에 저장시켜준다.
- 모든 연산을 끝냈다면 Wmin과 Bmin값 중 더 작은 값을 출력해준다.
코드
const fs = require('fs');
let [n, ...board] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');
let N = Number(n.trim().split(' ')[0]);
let M = Number(n.trim().split(' ')[1]);
let Wdot = new Set();
let Bdot = new Set();
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
//시작이 W
if (i % 2 === 0 && j % 2 === 0 && board[i].charAt(j) === 'B') {
Wdot.add(`${i},${j}`);
} else if (i % 2 === 0 && j % 2 !== 0 && board[i].charAt(j) === 'W') {
Wdot.add(`${i},${j}`);
} else if (i % 2 !== 0 && j % 2 === 0 && board[i].charAt(j) === 'W') {
Wdot.add(`${i},${j}`);
} else if (i % 2 !== 0 && j % 2 !== 0 && board[i].charAt(j) === 'B') {
Wdot.add(`${i},${j}`);
}
//시작이 B
if (i % 2 === 0 && j % 2 === 0 && board[i].charAt(j) === 'W') {
Bdot.add(`${i},${j}`);
} else if (i % 2 === 0 && j % 2 !== 0 && board[i].charAt(j) === 'B') {
Bdot.add(`${i},${j}`);
} else if (i % 2 !== 0 && j % 2 === 0 && board[i].charAt(j) === 'B') {
Bdot.add(`${i},${j}`);
} else if (i % 2 !== 0 && j % 2 !== 0 && board[i].charAt(j) === 'W') {
Bdot.add(`${i},${j}`);
}
}
}
let Wcount = 0;
let Wmin = 251;
let Bcount = 0;
let Bmin = 251;
for (let i = 0; i < N - 7; i++) {
for (let j = 0; j < M - 7; j++) {
Wcount = 0;
Bcount = 0;
for (let k = i; k <= i + 7; k++) {
for (let l = j; l <= j + 7; l++) {
if (Wdot.has(`${k},${l}`)) {
Wcount++;
}
if (Bdot.has(`${k},${l}`)) {
Bcount++;
}
}
}
if (Wmin > Wcount) Wmin = Wcount;
if (Bmin > Bcount) Bmin = Bcount;
}
}
console.log(Math.min(Wmin, Bmin));회고
정말 생각나는 방법이 이것뿐이었고... 마음에 정말 들지 않는 코드지만 정답이긴 했고, 어려웠던 문제이다보니 기록은 해야할 것 같아서 올려본다. 처음에는 시작점이 W, B일 때 잘못 그려진 갯수를 비교해서 더 작은 갯수를 가지게 되면 해당 경우가 정답에서 요구하는 경우라고 생각했다. 문제가 너무 복잡해서 설명하기도 어려운데.. 그냥 시작점이 W, B인 경우에 W의 경우에 잘못 그려진 갯수가 더 적으면 무조건 시작이 W일 것이다?라고 생각하고 풀이를 했다는 뜻이다.
그렇게 풀이했더니 문제 예제도 잘 나오는데 제출만 하면 틀렸다. 게시판에 있는 대부분의 반례를 다 적용했음에도 잘 나와서 멘탈이 나갔는데 딱 하나의 반례만 틀리게 나왔다.
8 33
BWWWWWBBWWBWBWBWWWWBBWWBWBBWBBWBB
WBBBWBBBBWBBBBBBBBWBWWBWWBBBBBBBW
WBWBWBBWWBWBBBWBBWBWWBWWBWWWWBBBW
WBBBBWWWWWBWBBWWBBBWBWWWWWWWWWWWW
WWWBWWBWWBBWBBBBWWWWWWWWWWBWBBWWW
WWWBWBWWBWWBWWBBWBWWWBWBBBBWBWBWB
BBBBBBWWBBBWWWWBBBBBWBWBWWBWBBWBB
WWWBBBWWBWWBBBBWBWWBWWWWBBWWWWBBB
answer : 28또 짜증나는 게 하필 출력 값은 29였던 것이다.. 조금만 건들면 해결될 것 같아서 코드 여러군데를 수정했지만 답과 점점 멀어졌고... 생각을 다시 해보니 다시 그려야하는 최소 개수가 아닌 정사각형의 최소 개수이 문제의 요점이다보니... 아무리 많이 수정되어야 해도 한 번에 가려지면 문제가 없겠구나를 깨닳았다... 휴... 생각해낸게 다행이다.
이번 문제는 도중에 다른 풀이를 참고하려고 했으나 참고를 못한 웃픈 문제였다. 그냥 문제 자체가 너무 구현할 것을 여러 개로 만들어놔서 그런지 다른 사람들의 풀이 방식을 이해하질 못하겠더라... 왜 저렇게 구현하지? 저건 뭔데 구현하지? 이렇게 생각하다가 그냥 스스로 풀어버렸는데 코드 퀄리티는 조금많이 별로인 것 같지만 그래도 해결 방법을 보지 않고 풀었으니까 잘했다고 생각한다. 굿.
