[Python 3] BOJ - 1018 "체스판 다시 칠하기"

 # 문제 링크 : https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 # 풀이 :

물론 각 칸의 경우에 대해 조사하는 것도 방법이지만 개인적으로는 애초에 검은색으로 시작하는 체스판과 흰색으로 시작하는 체스판, 즉 정답인 케이스 두가지를 미리 만들어 놓고 범위에 속하는 부분을 별도의 2차원 배열에 담아 각각의 정답과 다른 칸이면 각 경우(검은색으로 시작하거나 흰색으로 시작하거나)의 칠해야 하는 갯수를 1씩 증가시켜 더 작은 수를 리턴하도록 했다.

 예시)

<그림 1. 각 경우 별 결과>

 따라서 위 그림에서 검은색으로 시작하는 체스판과 현재(Temp)를 비교한다면, 파란색 X의 칸을 제외하고 모두 색깔이 다르므로 검은색으로 시작하는 체스판을 기준으로 했을 때 현재 체스판에서 "다시" 칠해야 하는 칸의 갯수는 63개이다. 그러나, 흰색에서 시작하는 체스판과 현재를 비교한다면 "다시" 칠해야 하는 칸의 수는 1개이다. 왜냐하면 빨간색 X칸을 제외하고는 이미 색이 모두 같기 때문이다. 따라서 현재의 경우는 흰색 체스판과 비교했을 때 더 작게 칠할 수 있다.

 

 # 코드

import sys
# 검은색으로 시작하는 정답 체스판, 흰색으로 시작하는 정답 체스판
start_black = []
start_white = []

# 최솟값을 찾기 위해 inf값 할당
ans = 10000000

# 각 정답 체스판 생성
for i in range(8):
    if i % 2 == 0:
        start_black.append(['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'])
        start_white.append(['W', 'B', 'W', 'B', 'W', 'B', 'W','B'])
    else:
        start_black.append(['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'])
        start_white.append(['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'])

# test : 범위에 속하지 않는 경우 -1 리턴, 속한다면 다시 칠해야하는 칸의 갯수 리턴
def test(x,y):
    correct_b = 0
    correct_w = 0
    # 인덱스 비교의 편의를 위해 임의의 2차원 배열에 원래 체스판의 값을 복사한다
    # <그림 1>의 Temp를 만드는 과정이다
    for_compare = []
    if 0 <= x + 8 <= n and 0 <= y + 8 <= m:
        for i in range(x, x + 8):
            temp = []
            for j in range(y, y + 8):
                temp.append(chess[i][j])
            for_compare.append(temp)

        for i in range(8):
            for j in range(8):
                if for_compare[i][j] != start_black[i][j]:
                    correct_b += 1

        for i in range(8):
            for j in range(8):
                if for_compare[i][j] != start_white[i][j]:
                    correct_w += 1
        # 각 경우 중 최소값 리턴
        return min(correct_w, correct_b)
    return -1


n, m = map(int, sys.stdin.readline().split())
chess = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
for i in range(n):
    for j in range(m):
        res = test(i,j)
        if res != -1:
            if res < ans:
                ans = res
print(ans)