1018 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

---

최대 크기가 50x50이다. 그 안에서 각 타일마다 8x8 범위를 스캔한다면 16만 회 정도로 순회하므로 브루트포스 알고리즘을 적용해도 괜찮다.

 

8x8 범위 내에서 최소 비용으로 칠하려면 체크무늬가 이미 잘 칠해져 있어야 한다.

 

체크무늬는 흰검흰검... 또는 검흰검흰 순으로 등장하므로 시작할 타일의 색에 따라 값을 스위칭해가며 검사하면 된다.

 

그러므로 한 칸 씩 이동할 때마다 tile값을 스위칭해 올바르게 등장하는지 검사한다. 

char tile = 'W';
startedWithWhiteCount = 0;
startedWithBlackCount = 0;
for (int k = 0; k < 8; k++) {
    for (int l = 0; l < 8; l++) {
        if (tile == board[k][l]) {
            startedWithWhiteCount++;
        }
        else {
            startedWithBlackCount++;
        }
        if (l < 7) {
            if (tile == 'B') {
                tile = 'W';
            }
            else {
                tile = 'B';
            }
        }
    }
}

만약 흰검흰검순으로 등장한다면, 한 칸 씩 이동할 때마다 startedWithWhiteCount가 누적될 것이다.

반대의 경우 startedWithBlackCount가 누적될 것이다. 

반복을 64회 하면서 누적시키기 때문에 둘의 합은 항상 64다.

 

그리고 l<7을 왜 검사하냐면, 8번째 칸의 색이 다시 다음줄의 첫째 칸에 등장하기 때문이다. 이 경우 스위칭을 하지 않는다.

이제 누적된 값들중 최소값을 찾고 모든 범위에서 최소값을 갱신하면 된다. 

 

사진처럼 검은색타일로 시작했다고 가정하고 체크무늬가 잘 나타나있다면 startedWithBlackCount가 64일 것이다.

 

만약 한 개의 타일이 체크무늬에 어긋나있다면 startedWithBlackCount는 63이고 startedWithWhiteCount는 1일 것이다.

 

이 말은 63개의 타일을 바꾸기 보다 1개의 타일을 바꾸는게 정답이라는 말이다.

 

이 과정을 모든 타일에 대해 수행한다. 단, 8x8 범위를 유지하면서 수행해야한다.

#include <iostream>
using namespace std;
int main() {
    int x, y, startedWithWhiteCount = 0, startedWithBlackCount = 0, min = 64;
    cin >> y >> x;

    char** board = new char* [y];
    for (int i = 0; i < y; i++) {
        board[i] = new char[x + 1];
        cin >> board[i];
    }

    for (int i = 0; i <= y - 8; i++) {
        for (int j = 0; j <= x - 8; j++) {
            char tile = 'W';
            startedWithWhiteCount = 0;
            startedWithBlackCount = 0;
            for (int k = 0; k < 8; k++) {
                for (int l = 0; l < 8; l++) {
                    if (tile == board[i + k][j + l]) {
                        startedWithWhiteCount++;
                    }
                    else {
                        startedWithBlackCount++;
                    }
                    if (l < 7) {
                        if (tile == 'B') {
                            tile = 'W';
                        }
                        else {
                            tile = 'B';
                        }
                    }
                }
            }
            if (startedWithWhiteCount < min) {
                min = startedWithWhiteCount;
            }
            if (startedWithBlackCount < min) {
                min = startedWithBlackCount;
            }
        }
    }

    cout << min;

    for (int i = 0; i < y; i++) {
        delete[] board[i];
    }
    delete[] board;
}

솔직히 구현문제라 그런지 깔끔한 방법이 더 있을 것 같다. 그냥.. 맞추기 위해 풀었다.