백준 1018 체스판 다시 칠하기 C++

🧠 백준 1018 – 체스판 다시 칠하기

내가 겪은 착각, 실수, 그리고 개선까지
“틀린 건 내 코드가 아니라, 그때의 내 사고였다.”

---

📌 문제 설명

N×M 크기의 보드가 있습니다.
각 칸은 'W' 또는 'B'로 칠해져 있고,
지민이는 이 보드에서 8×8 체스판 모양의 조각을 잘라내어
정상적인 체스판 형태로 만들고 싶어 합니다.

정상적인 체스판이란 다음 두 가지 패턴 중 하나입니다:

• 왼쪽 위 칸이 'W'이고, W/B가 번갈아 나오는 체스판
• 왼쪽 위 칸이 'B'이고, B/W가 번갈아 나오는 체스판

보드의 어느 위치에서든 8×8 크기로 잘라낼 수 있습니다.
지민이는 그 조각이 체스판이 아니면, 몇몇 칸을 다시 칠해서 체스판으로 만들 수 있습니다.
이때, 다시 칠해야 하는 칸의 수의 최솟값을 구하는 것이 이 문제의 목표입니다.

---

🧠 내가 처음 떠올린 전략

문제를 처음 읽고 떠오른 전략은 단순했습니다.

정답 체스판은 항상 두 가지니까,
정답 체스판을 두 개 만들어두고
입력 보드에서 가능한 모든 8x8 조각을 잘라서
각각 비교해보면 되지 않을까?

• arr: 입력 받은 보드
• arr2: W로 시작하는 정답 체스판
• arr3: B로 시작하는 정답 체스판
• 보드 전체에서 가능한 모든 8×8 조각에 대해
  • 각각 arr2, arr3과 비교
  • 다시 칠해야 하는 칸 개수를 세고
  • 가장 적은 값으로 갱신해 저장

---

💻 내가 작성한 전체 C++ 코드

#include <iostream>
using namespace std;

int main(void)
{
	int N, M, check1 = 0, check2 = 0, min_check = 50000;
	cin >> N >> M;
	char arr[50][50], arr2[50][50], arr3[50][50];

	// 입력
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> arr[i][j];

	// arr2: W로 시작하는 체스판
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			arr2[i][j] = (i + j) % 2 == 0 ? 'W' : 'B';

	// arr3: B로 시작하는 체스판
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			arr3[i][j] = (i + j) % 2 == 0 ? 'B' : 'W';

	// 8x8 비교
	for (int k = 0; k <= N - 8; k++) {
		for (int p = 0; p <= M - 8; p++) {
			check1 = 0, check2 = 0;
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8; j++) {
					if (arr[k + i][p + j] != arr2[i][j]) check1++;
					if (arr[k + i][p + j] != arr3[i][j]) check2++;
				}
			}
			int local_check = min(check1, check2);
			if (min_check > local_check)
				min_check = local_check;
		}
	}

	cout << min_check << endl;
	return 0;
}

---

❗ 내가 겪었던 실수와 착각

❌ 1. 시작 색으로 체스판 유형을 판단하려 했다

입력 보드는 이미 잘못 칠해졌을 수 있습니다.
정답이 W로 시작일 수도, B로 시작일 수도 있습니다.
→ 두 가지 체스판 모두 비교해야 합니다.

❌ 2. min_check 값을 조건 없이 덮어썼다

if (check1 < check2)
	min_check = check1;
else
	min_check = check2;

→ 앞에서 나온 더 작은 값을 덮어버릴 수 있습니다.
→ 수정 코드:

int local_check = min(check1, check2);
if (min_check > local_check)
	min_check = local_check;

---

✅ 개선점 – 왜, 무엇을, 어떻게 바꿔야 했는가?

🧩 고민: 정답 체스판을 굳이 배열로 만들 필요 있을까?

체스판은 (i + j) % 2 값이 0이면 시작 색, 1이면 반대 색입니다.
즉, 배열로 미리 만들어둘 필요 없이, 그때그때 계산하면 됩니다.

---

❓ (i + j) % 2 수식이 이해 안 됐을 때

처음엔 정말 이게 이해가 안 갔습니다.

char expected1 = ((i + j) % 2 == 0) ? 'W' : 'B';
char expected2 = ((i + j) % 2 == 0) ? 'B' : 'W';

직접 표를 그려보며 이해했습니다:

좌표(i,j)	i+j	(i+j)%2	W로 시작할 때 색
(0,0)	0	0	W
(0,1)	1	1	B
(1,0)	1	1	B
(1,1)	2	0	W

→ 짝수일 때는 시작 색, 홀수일 때는 반대 색
→ 이 논리로 모든 칸의 정답 색을 계산할 수 있습니다!

---

💻 개선된 전체 C++ 코드

#include <iostream>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    char board[50][50];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> board[i][j];

    int min_check = 64;

    for (int i = 0; i <= N - 8; i++) {
        for (int j = 0; j <= M - 8; j++) {
            int repaint_W = 0;
            int repaint_B = 0;

            for (int x = 0; x < 8; x++) {
                for (int y = 0; y < 8; y++) {
                    char current = board[i + x][j + y];

                    char expected1 = ((x + y) % 2 == 0) ? 'W' : 'B';
                    char expected2 = ((x + y) % 2 == 0) ? 'B' : 'W';

                    if (current != expected1) repaint_W++;
                    if (current != expected2) repaint_B++;
                }
            }

            int local_min = min(repaint_W, repaint_B);
            min_check = min(min_check, local_min);
        }
    }

    cout << min_check << endl;
    return 0;
}

---

🔍 개선된 코드 해설

• expected1: W로 시작할 때 해당 칸이 가져야 할 색
• expected2: B로 시작할 때 해당 칸이 가져야 할 색
• repaint_W, repaint_B: 각각 다시 칠해야 하는 칸 수
• (x + y) % 2: 색을 번갈아 계산하는 규칙

---

🎯 요약 비교

항목	내가 처음 한 방식	개선된 방식
체스판 생성 방식	배열 두 개 (arr2, arr3) 생성	수식으로 계산 (expected1,2)
비교 방법	배열과 하나하나 비교	수식으로 즉석에서 비교
메모리 사용량	더 많이 사용됨	배열 없이, 덜 사용됨
코드 길이	길고 반복적임	간결하고 읽기 쉬움

---

🧑‍💻 최종 회고

이 문제는 단순 구현 문제가 아니었습니다.
정답 체스판의 규칙을 정확히 이해하고, 일반화할 수 있느냐가 핵심이었습니다.

처음엔 배열을 직접 만들어 비교했고,
그 과정에서 수많은 실수를 했지만
그 덕분에 (i + j) % 2의 의미와
체스판이라는 구조 자체를 더 깊이 이해하게 되었습니다.

“틀린 건 내 코드가 아니라, 그때의 내 사고였다.”
그리고 지금은 더 나은 사고를 하고 있습니다.