백준 1018번 [체스판 다시 칠하기](C++)-yes6686- 티스토리

백준 문제 풀이: 1018 [체스판 다시 칠하기]

---

문제 링크: https://www.acmicpc.net/problem/1018

문제 설명:

주어진 n×m 크기의 보드에서 8×8 크기의 체스판으로 잘라냈을 때, 체스판의 색상 패턴과 다르게 칠해진 칸의 최소 개수를 구하는 문제입니다. 체스판의 색상 패턴은 다음 두 가지입니다:

• 왼쪽 위 칸이 흰색으로 시작하는 체스판
• 왼쪽 위 칸이 검은색으로 시작하는 체스판

보드에서 8×8 크기의 부분을 반복적으로 확인하며, 칠해야 하는 최소 칸 수를 계산합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

char c[51][51];
char arrw[8][8] = { 
    {'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'}
};
char arrb[8][8] = { 
    {'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'}
};

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c[i][j];
        }
    }

    int min = 2500; // 큰 값으로 초기화
    for (int i = 0; i <= n - 8; i++) {
        for (int j = 0; j <= m - 8; j++) {
            int cntw = 0, cntb = 0;
            for (int t = 0; t < 8; t++) {
                for (int h = 0; h < 8; h++) {
                    if (c[i + t][j + h] != arrw[t][h]) cntw++;
                    if (c[i + t][j + h] != arrb[t][h]) cntb++;
                }
            }
            min = std::min(min, std::min(cntw, cntb));
        }
    }
    cout << min << endl;
}

---

코드 설명

• 핵심 아이디어: 체스판의 두 가지 패턴을 저장하고, 보드의 모든 8×8 영역을 순회하며 칠해야 하는 최소 칸 수를 계산합니다.
• 구현 세부사항:
  • 배열 arrw와 arrb는 각각 흰색과 검은색으로 시작하는 체스판을 정의합니다.
  • 이중 루프를 통해 모든 가능한 8×8 영역을 탐색합니다.
  • 각 영역에 대해 cntw와 cntb를 계산해 최소값을 갱신합니다.
• 시간 복잡도: O(n × m × 64)
  • n × m 크기의 보드를 탐색하며, 각 8×8 영역의 칸을 비교합니다.

---

결과

주어진 보드에서 체스판을 만들기 위해 칠해야 하는 최소 칸 수를 정확히 계산합니다. 최적화된 반복문을 사용하여 효율적으로 동작합니다.

다른 접근 방식이나 궁금한 점이 있다면 알려주세요!