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

[BOJ] 1018번 체스판 다시 칠하기 문제

처음 보면 엄청 당혹스러운 브루트 포스 문제다.

먼저, 브루트 포스(Brute force)는 말 그대로 무차별 대입을 뜻하며, 어떠한 규칙을 구하는 것이 아닌 모든 경우의 수를 따지는 방법이다.

모든 경우의 수를 따지다 보니 $N$이 적당히 작아야 하며, 실행 시간도 $N$에 맞게 커야 한다. 이 문제의 경우엔 2초로 설정되어 있다.

만약 $N$이 크거나 시간이 짧다면 브루트 포스를 하면 안 되고, 그리디 알고리즘이나 특정 알고리즘을 사용해야 한다.

$N$이 적당히 작아 보이고, 그에 맞거나 약간 긴 시간 제한이 주어지며, 바로 떠오르는 알고리즘이 없다면 주로 브루트 포스를 사용하게 된다. 모두 다 대입하는게 컴퓨터를 배우는 입장에서 덜 떨어져 보일 수도 있겠으나, 되려 컴퓨터는 이런 노가다를 인간 대신에 하기 위해 태어났고 이러한 노가다를 인간보다 월등히 잘하니 항상 배제해야 하는 알고리즘이 아니라는 것을 알아두자. 실제로 상위권 문제 중에서도 의도한 알고리즘이 아닌 나이브(naïve)하게 브루트 포스로 뚫린 케이스가 종종 있다.

이 문제는 빅-오 표기법(Big-O notation)의 감을 잡아주는 아주 좋은 문제다.

---

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().rstrip().split())
    chess = list()
    for _ in range(N):
        chess.append(list(sys.stdin.readline().rstrip()))

    min_square = 65
    for i in range(N-7):
        for j in range(M-7):
            W_first, B_first = 0, 0
            for k in range(8):
                for l in range(8):
                    if (k+l)%2 == 0:
                        if chess[i+k][j+l] == 'B':
                            W_first += 1
                        else:
                            B_first += 1
                    else:
                        if chess[i+k][j+l] == 'W':
                            W_first += 1
                        else:
                            B_first += 1

            min_square = min(min_square, W_first, B_first)

    print(min_square)

 

먼저 큰 루프가 두개 있는데, 하나는 $i$와 $j$로 이루어진 시작점 루프, 다른 하나는 그 안에 있는 $k$와 $l$로 이루어진 $8\times 8$ 체스판을 도는 루프다.

시작점 루프가 돌 때 마다 첫 원소가 'W'로 시작할 때의 고쳐야 하는 변수를 W_first, 'B'일 때를 B_first로 둔다.

그리고 $k$와 $l$로 $8\times 8$ 체스판을 도는데, 이 둘의 합이 짝수(0도 포함)일 때와 홀수일 때가 체스판 무늬와 같아짐을 이용한다. 체스판의 $(N-7)\times (M-7)$개의 시작점을 돌 때마다 W_first와 B_first가 아닐 때의 횟수를 구해 최소로 고쳐야 하는 횟수를 갱신해간다.

주의해야 할 점은 W_first와 B_first는 시작점이 바뀔 때마다 초기화해야 하고, 시작점 마다의 W_first와 B_first를 구해서 min_square를 갱신해야 한다는 것이다.

그것이 브루트 포스니까

min_square는 65로 설정해도 된다. 최대 수정 가능 횟수가 64이기 때문에 시작점의 루프를 한 번이라도 돈다면 min_square는 65보다 무조건 작아진다.

---

이 문제의 핵심은 $N\times M$의 체스판에서 $8\times 8$만을 본다는 것과, 그 $8\times 8$에서의 첫 원소가 'W'거나 'B'일 때의 다시 칠해야 하는 경우의 수를 전부 구해야 한다는 것이다.

즉, 최악의 계산 횟수는 $N$과 $M$이 전부 50일 때이고, 이때의 총 루프의 횟수는 $43\times 43\times 8\times 8=118,336$번이다. 최악의 계산 횟수가 10만 회 근처고, 2초가 주어졌기 때문에 충분히 브루트 포스를 사용할 수 있다. 아마 1초였어도 풀 수 있는 문제일 듯하지만 여러 사정상 2초로 뒀을 가능성이 크다.

여기서 43은 $N$과 $M$이 전부 50일 때 확인해야 하는 총 가로/세로 길이이고, 8은 체스판 크기인 $8\times 8$에서의 8이다.