[BOJ 1018] 체스판 다시 칠하기 - [브루트 포스]

[BOJ 1018] 체스판 다시 칠하기 - [브루트 포스]

문제 링크

https://www.acmicpc.net/problem/1018

문제 요약

$N \times M$ 크기의 보드에서 $8 \times 8$ 크기의 체스판을 잘라내어, 인접한 칸의 색이 겹치지 않도록 다시 칠해야 하는 칸의 최소 개수를 구하는 문제입니다.

접근 방법

• 자료구조: 2차원 문자열 배열 (std::vector<std::string>)
• 알고리즘: 브루트 포스 (Brute Force)
• 핵심 아이디어: - 체스판이 가질 수 있는 완성된 형태는 딱 두 가지(맨 왼쪽 위가 'W'인 경우와 'B'인 경우)뿐입니다.
  • 보드 내에서 $8 \times 8$로 자를 수 있는 모든 경우의 수를 순회하며, 두 가지 완성 형태와 비교하여 최소 수정 횟수를 갱신합니다.

풀이 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 체스판의 두 가지 정석 패턴 정의
string whiteFirst[8] = {
    "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW",
    "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW"
};

string blackFirst[8] = {
    "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB",
    "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB"
};

int getRepaintCount(const vector<string>& board, int startY, int startX) {
    int countW = 0;
    int countB = 0;

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            // (startY, startX)부터 시작하는 8x8 영역을 정석 패턴과 비교
            if (board[startY + i][startX + j] != whiteFirst[i][j]) countW++;
            if (board[startY + i][startX + j] != blackFirst[i][j]) countB++;
        }
    }
    // 두 패턴 중 더 적게 칠해도 되는 횟수 반환
    return min(countW, countB);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<string> board(N);
    for (int i = 0; i < N; i++) {
        cin >> board[i];
    }

    int minResult = 64; // 8x8에서 칠할 수 있는 최대값

    // 보드 안에서 8x8을 만들 수 있는 모든 시작 지점 탐색
    for (int i = 0; i <= N - 8; i++) {
        for (int j = 0; j <= M - 8; j++) {
            minResult = min(minResult, getRepaintCount(board, i, j));
        }
    }

    cout << minResult << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O((N-7) \times (M-7) \times 8 \times 8)$
  • $N, M$의 최대값이 50이므로 약 $43 \times 43 \times 64 \approx 118,336$번의 연산이 수행됩니다. 이는 시간 제한 내에 충분히 가능합니다.
• 공간 복잡도: $O(N \times M)$
  • 보드 정보를 저장하기 위한 공간이 필요합니다.

실행 결과

• 메모리: 2024 KB
• 시간: 0 ms (C++ 기준)

핵심 포인트

1. $8 \times 8$ 영역의 맨 왼쪽 위가 'W'인 경우와 'B'인 경우를 모두 고려해야 합니다.
2. 보드의 크기가 크지 않기 때문에 브루트 포스 방식을 통해 모든 경우를 확인하는 것이 가장 확실한 방법입니다.
3. min(countW, countB)를 사용하여 한 영역에 대해 두 패턴 중 최적의 결과를 추출합니다.

예제 확인

• 예제 1 (8x8 WB 반복): 모든 칸이 이미 체스판 형태이므로 출력값은 0이 나옵니다.
• 예제 2 (10x13): 전체 보드를 순회하며 $8 \times 8$을 잘랐을 때, 최소 7칸만 고치면 되는 영역을 찾아냅니다.