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

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

1018번: 체스판 다시 칠하기

1. 문제 접근

가로세로에 칸이 8보다 같거나 많은 사각형보드로 8x8의 체스판을 만드는 문제이다. 우선 뭐 무식할 수도 있는데 가장 먼저 생각할 수 있는 방법은 모든 가능한 위치에서 바꿔야하는 색깔갯수를 구해 가장 작은 수를 출력하는 방법이 있다. 이 방법을 적용시키기 위해서는 문제에서 주어진 시간안에 가능한지 시간복잡도를 한번 계산해 봐야한다.

 

시간복잡도 계산 

NxM 보드에서 서로다른 8x8 사각형은 모두 (N - 8 + 1) x (M - 8 + 1)개 이다. 또 각 8x8사각형에서 8x8=64개의 칸에 색깔을 모두 비교해 봐야하고 검은색으로 시작하는 체스판과 흰색으로 시작하는 체스판, 이렇게 2가지 종류가 있다는 것을 고려하면 아래와 같이 시간복잡도를 구할 수 있다. 이는 주어진시간 2초동안 너무나 충분한 계산 횟수이기에 위 방법을 사용하여 문제를 풀어보았다.

시간복잡도 = (N - 8 + 1) x (M - 8 + 1) x 64 x 2 = 236,672 번 (N, M의 최댓값은 50)

 

 

 

2. 코드

#include<iostream>
using namespace std;

#define MAX_NM 50
#define MAX_COUNT 64
#define BLACK 'B'
#define WHITE 'W'

int getChangeCountWithStartColor(char board[][MAX_NM], int n, int m, char startColor) {
    int changeCount = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if ((i + j) % 2 == 0) {
                if (board[n + i][m + j] != startColor)
                    changeCount++;
            }
            else {
                if (board[n + i][m + j] == startColor)
                    changeCount++;
            }
        }
    }

    return changeCount;
}

int getChangeCount(char board[][MAX_NM], int n, int m) {
    int changeCount_startBlack = getChangeCountWithStartColor(board, n, m, BLACK);
    int changeCount_startWhite = getChangeCountWithStartColor(board, n, m, WHITE);

    if (changeCount_startBlack < changeCount_startWhite)
        return changeCount_startBlack;
    else
        return changeCount_startWhite;
}

int main() {
    char board[MAX_NM][MAX_NM];
    int N, M;
    int minChangeCount = MAX_COUNT;

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

    for (int i = 0; i < (N - 8 + 1); i++) {
        for (int j = 0; j < (M - 8 + 1); j++) {
            int tempChangeCount = getChangeCount(board, i, j);
            if (tempChangeCount < minChangeCount)
                minChangeCount = tempChangeCount;
        }
    }

    cout << minChangeCount << endl;

    return 0;
}