[백준] 1018번 - 체스판 다시 칠하기

www.acmicpc.net

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

문제

💡

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

시간 제한: 2초

메모리 제한: 128MB

입력

💡

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

💡

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

예제 입력	예제 출력
8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	1
10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB	12
8 8 BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB	0

풀이

8*8 체스판을 잘라 색칠해야 하는 횟수를 구하고 그 중 가장 적은 횟수를 구한다.

모든 상황에서 모든 경우의수를 확인해 최솟값을 구해야 하기 때문에 타뷸레이션 방식으로 풀었다.

반복문을 사용해 연산했을 때 시간복잡도를 계산해 보았다.

보드의 최대 크기는50*50, 체스판의 크기는 8*8 고정, 체스판 각 블럭을 탐색해야 하므로

43^2 * 8^4 = 7,573,504회 연산이 필요하고 시간 제한에 걸리지 않는다.

첫번째 블럭의 색상이 B인 경우와 W인 경우 패턴이 달라지므로 두 가지 경우로 나누어 계산한다.

입력받은 배열이 체스판 이상의 크기이므로 자를 수 있는 경우의수를 반목문으로 구해 복사했다.

가로 인덱스와 세로 인덱스의 합이 홀수인 블럭과 짝수인 블럭은 각각 같은 색상을 가진다는 특징이 있다.

이를 삼항 연산자를 통해 횟수를 센 뒤 최솟값을 구한다.

코드


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
using namespace std;

int check(const vector<vector<char>>& board, char scolor) {
    int count = 0;
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            char tmp = ((i + j) % 2 == 0) ? scolor : (scolor == 'B' ? 'W' : 'B');
            if (board[i][j] != tmp) count++;
        }
    }

    return count;
}

int main() {
    int n, m, tmp, ans = 64;
    cin >> n >> m;
    cin.ignore();
    vector<vector<char>> adj(n, vector<char>(m));
    vector<vector<char>> board(8, vector<char>(8));

    for (int i = 0; i < n; ++i) {
        string s;
        getline(cin, s);
        for (int j = 0; j < m; ++j) {
            adj[i][j] = s[j];
        }
    }

    for (int i = 0; i < n - 7; ++i) {
        for (int j = 0; j < m - 7; ++j) {
            for (int k = 0; k < 8; ++k) {
                for (int l = 0; l < 8; ++l) {
                    board[k][l] = adj[k + i][l + j];
                }
            }
            int tmp1 = check(board, 'B');
            int tmp2 = check(board, 'W');
            int tmp = min(tmp1, tmp2);
            if (tmp < ans) {
                ans = tmp;
            }
        }
    }

    cout << ans;

    return 0;
}