백준 1018

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

코드를 작성하진 못했고, 떠올린 아이디어는..

가능한 8X8 체스판은 총 2개이므로,

chess_1 = ['WBWBWBWB', 'BWBWBWBW'] * 4
chess_2 = ['BWBWBWBW', 'WBWBWBWB'] * 4

주어진 보드에서 잘라낼 수 있는 8X8 보드를 각각 chess_1, chess_2와 비교해서 다른 칸의 개수를 찾으면서 최솟값을 업데이트 하는 방식이다.

https://velog.io/@yj_lee/백준-1018번-체스판-다시-칠하기-파이썬
위의 링크를 참고해서 작성한 정답 코드는 다음과 같다.

import sys

N, M = map(int, sys.stdin.readline().split())

board = []
for _ in range(N):
    board.append(sys.stdin.readline().rstrip())

result = []
for i in range(N - 7):
    for j in range(M - 7):
        case_1 = 0  # case 1: 좌표 합이 홀수인 지점이 W인 경우
        case_2 = 0  # case 2: 좌표 합이 짝수인 지점이 B인 경우

        for s in range(i, i + 8):
            for t in range(j, j + 8):
                if (s + t) % 2 == 1:    # 좌표 합이 홀수
                    # case 1
                    if board[s][t] == 'B':
                        case_1 += 1
                    # case 2
                    if board[s][t] == 'W':
                        case_2 += 1
                else:                   # 좌표 합이 짝수
                    # case 1
                    if board[s][t] == 'W':
                        case_1 += 1
                    if board[s][t] == 'B':
                        case_2 += 1

        result.append(min(case_1, case_2))

print(min(result))

완전 탐색 알고리즘(Brute-force algorithm)답게 주어진 보드에서 잘라낼 수 있는 모든 8X8 보드를 탐색했다.

이 탐색 과정에서 사용한 아이디어는 신박하게 느껴졌다.

시작점이 W, B인 경우로 나누는 것이라기보다는..
체스판의 조건이 인접한 칸은 서로 다른 색이어야 하는데, 이는 결국 가로, 세로 좌표 값의 합이 홀수인 경우와 짝수인 경우의 색(W, B)이 달라야 한다는 의미이다.

그래서 주어진 보드에서 어떤 8X8 보드를 잘랐을 때,

• case 1: 좌표 합이 홀수인 경우가 W
• case 2: 좌표 합이 홀수인 경우가 B

로 경우를 나누면,

좌표 합이 홀수인 경우에,
case 1에서는 그 칸의 값이 B이면 색을 바꿔야 원하는 체스판이 되므로 case_1 += 1을 해주고,
case 2에서는 그 칸의 값이 W이면 B로 바꿔줘야 하므로 case_2 += 1을 해준다.

좌표 합이 짝수인 경우는 반대로 생각하면 된다.

이러한 값(체스판을 만들기 위해 색칠하는 횟수)을 result 리스트에 저장하면서 완전 탐색을 수행하고, 결과적으로 min(result)가 색을 가장 적게 바꾸면서 체스판을 만드는 케이스가 된다.