📌 문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
| 입력 | 출력 |
|---|---|
| 8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW | 1 |
| 10 13 BBBBBBBBWBWBW BBBBBBBBWBWBW BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB | 12 |
✨ 해결 방법
M x N 크기의 보드에서 8 x 8 크기의 체스판을 만들려고 한다. 체스판은 반드시 검은색(B)과 흰색(W)이 번갈아가며 칠해져야 한다. 따라서 원본 보드를 8x8 크기로 자를 때, 다시 칠해야 하는 최소 칸 수를 구하는 문제이다.
체스판을 올바르게 색칠하는 경우는 두 가지 경우 뿐이다.
1. 왼쪽 상단이 흰색(W)로 시작하는 체스판
2. 왼쪽 상단이 검은색(B)로 시작하는 체스판
즉, 각 8x8 구역을 두 개의 패턴과 비교해서 몇 개를 다시 칠해야 하는지 계산한 후, 최소값을 찾으면 된다.
💻 solution 1
const [size, ...chess] = require('fs').readFileSync("/dev/stdin").toString().trim().split(/\r?\n/);
const [N, M] = size.split(' ').map(Number); // row, column의 사이즈
let minimum = Infinity; // 최종 출력할 최솟값
for (let i = 0; i <= N - 8; i++) { // 열(i)의 시작점
for (let j = 0; j <= M - 8; j++) { // 행(y)의 시작점
let countWhite = 0; // W로 시작하는 체스판으로 변경해야 할 개수
let countBlack = 0; // B로 시작하는 체스판으로 변경해야 할 개수
for (let x = 0; x < 8; x++) { // 8×8 체스판의 열
for (let y = 0; y < 8; y++) { // 8×8 체스판의 행
const square = chess[i + x][j + y]; // 현재 칸의 색
if ((x + y) % 2 === 0) {
// (x+y)가 짝수면 'W'가 있어야 함 (W 시작 체스판 기준)
if (square !== 'W') countWhite++;
if (square !== 'B') countBlack++;
} else {
// (x+y)가 홀수면 'B'가 있어야 함 (W 시작 체스판 기준)
if (square !== 'B') countWhite++;
if (square !== 'W') countBlack++;
}
}
}
minimum = Math.min(minimum, countWhite, countBlack);
}
}
console.log(minimum);1. 8×8 체스판을 탐색하기 위한 이중 for문
for (let i = 0; i <= N - 8; i++) {
for (let j = 0; j <= M - 8; j++) {우선 2중 for문을 통해 검사할 범위를 한정한다.
만약 가로로 10칸, 세로로 13칸이 있다고 할 때, 검사할 수 있는 체스판의 경우의 수는 가로로 첫 번째 칸부터 세 번째 칸이 시작 점일 때, 그리고 세로로 0번째 칸부터 여섯 번째 칸이 시작 점일 때일 것이다. 가로로 네 번째 칸까지 넘어가게 된다면 8칸을 채울 수 없기 때문에 뒤로 넘어갈 수는 없다.
→ 시작점 i는 N-8까지, j는 M-8까지 반복
→ 즉, (i, j)는 8×8 영역의 좌측 상단 모서리
2. 두 가지 체스판 패턴과 비교
let countWhite = 0; // W로 시작하는 체스판으로 변경해야 할 개수
let countBlack = 0; // B로 시작하는 체스판으로 변경해야 할 개수현재 체스판을 W로 시작하는 상태로 바꾸는 게 나을지, B로 시작하는 상태로 바꾸는 게 나을지 각각 세어 비교한다.
3. 체스판을 하나씩 확인하면서 변경해야 하는 개수 세기
for (let x = 0; x < 8; x++) {
for (let y = 0; y < 8; y++) {
const square = chess[i + x][j + y]; // 현재 칸의 색첫 번째 칸부터 8칸을 자를 것이기 때문에 9번째 칸은 검사할 수 없다.
(i, j)를 기준으로 8×8 크기의 체스판을 검사한다.
chess[i + x][j + y]는 현재 위치의 색을 의미한다. (B or W)
4. 패턴과 비교하기
if ((x + y) % 2 === 0) {
// (x+y)가 짝수면 'W'가 있어야 함 (W 시작 체스판 기준)
if (square !== 'W') countWhite++;
if (square !== 'B') countBlack++;
} else {
// (x+y)가 홀수면 'B'가 있어야 함 (W 시작 체스판 기준)
if (square !== 'B') countWhite++;
if (square !== 'W') countBlack++;
}W로 시작하는 체스판이라고 가정했을 때, W이어야 하는 칸은 어디일까?
우선 (0,0)의 첫 번째 칸이 같아야 하며, 한 칸을 띄우고 우측으로 이동해야 한다. 아랫 줄의 경우 바로 아래 칸의 양옆 좌우가 같아야 한다. 이는 즉, x와 y가 모두 홀수이거나, 모두 짝수일 때를 의미한다. (2,2) (1,3) (0,4)...
모두 홀수거나 짝수라는 것은, x+y가 짝수이라는 것을 의미한다.
따라서 짝수일 때 같은지, 홀수일 때 다른지를 검사해야 한다.
-
(x + y) % 2 === 0이면, 현재 칸이 'W'여야 함
→ W가 아니면countWhite증가
→ B가 아니면countBlack증가 -
(x + y) % 2 !== 0이면, 현재 칸이 'B'여야 함
→ B가 아니면countWhite증가
→ W가 아니면countBlack증가
5. 최소 색칠 개수 갱신
minimum = Math.min(minimum, countWhite, countBlack);이 모든 경우의 수와, 이전의 값을 비교하여 가장 최소값을 구한다.
💻 solution2
체스판이 만들어지는 경우의 수는 W로 시작하느냐, B로 시작하느냐 총 두 가지 방법 뿐이다. 따라서 하드 코딩을 통해 더 간단하게 계산하도록 개선할 수 있다.
const [size, ...chess] = require('fs').readFileSync("/dev/stdin").toString().trim().split(/\r?\n/);
const [N, M] = size.split(' ').map(Number);
let minimum = Infinity;
// 기준 패턴 정의
const whiteStart = ['WBWBWBWB', 'BWBWBWBW'];
const blackStart = ['BWBWBWBW', 'WBWBWBWB'];
for (let i = 0; i <= N-8; i++){
for (let j = 0; j <= M-8; j++){
let countWhite = 0; // W 시작 체스판으로 변경해야 할 개수
let countBlack = 0;
for (let x = 0; x < 8; x++) {
for (let y = 0; y < 8; y++) {
const square = chess[i + x][j + y];
if (square !== whiteStart[x % 2][y]) countWhite++; // W 시작과 비교
if (square !== blackStart[x % 2][y]) countBlack++;
}
}
minimum = Math.min(minimum, countWhite, countBlack);
}
}
console.log(minimum);1. (x + y) % 2 방식 대신, 미리 패턴을 만들어두기
체스판은 한 줄이 W로 시작하면 다음 줄은 B로 시작해야 한다.
즉, W로 시작하는 패턴과 B로 시작하는 패턴을 반복해야 한다.
✅ W로 시작하는 체스판
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW1번째 줄은 W로 시작 (WBWBWBWB) 2번째 줄은 B로 시작 (BWBWBWBW) 3번째 줄은 W로 시작 (WBWBWBWB) ... → 이걸 배열로 만들면?
const whiteStart = ['WBWBWBWB', 'BWBWBWBW'];- 짝수 번째 줄(0, 2, 4, 6...) →
whiteStart[0] = 'WBWBWBWB' - 홀수 번째 줄(1, 3, 5, 7...) →
whiteStart[1] = 'BWBWBWBW'
B로 시작하는 체스판도 반대 경우로 패턴이 같기 때문에 둘 다 적으면 아래와 같다.
const whiteStart = ['WBWBWBWB', 'BWBWBWBW'];
const blackStart = ['BWBWBWBW', 'WBWBWBWB'];- whiteStart → 'W'로 시작하는 체스판의 두 가지 줄 패턴
- blackStart → 'B'로 시작하는 체스판의 두 가지 줄 패턴
이제 이 패턴을 사용해서 현재 칸의 색이 제대로 되어 있는지 바로 비교할 수 있다.
2. 패턴과 직접 비교하여 색칠해야 하는 개수 세기
for (let x = 0; x < 8; x++) {
for (let y = 0; y < 8; y++) {
const square = chess[i + x][j + y]; // 현재 칸의 색
if (square !== whiteStart[x % 2][y]) countWhite++; // W 시작 체스판과 비교
if (square !== blackStart[x % 2][y]) countBlack++; // B 시작 체스판과 비교
}
}whiteStart[x % 2][y]
→ x가 짝수일 때는 whiteStart[0]='WBWBWBWB', 홀수일 때는 whiteStart[1]='BWBWBWBW'
→ y 번째 문자를 가져와 현재 칸과 비교
→ 다르면 countWhite++
예를 들어, 현재 검사하는 체스판이 아래와 같고, x = 1, y = 0이라면,
BBWBWBWB
WBWBWBWB
BBWBWBWB
.....- 현재 칸
chess[1][0]= W - 올바른 색 (whiteStart[1][0]) = B ❌ →
countWhite++ - 올바른 색 (blackStart[1][0]) = W ✅
3. Math.min을 사용해 최솟값 갱신
minimum = Math.min(minimum, countWhite, countBlack);- white로 시작하는 체스판으로 바꿔야 하는 개수
countWhite - black으로 시작하는 체스판으로 바꿔야 하는 개수
countBlack
이 둘 중 더 적게 색칠해야 하는 경우와 기존 최소값을 비교해서 갱신한다.
