[백준 파이썬 1018] 체스판 다시 칠하기 (실버 4)

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

1018번: 체스판 다시 칠하기

import sys

N, M = map(int, input().split()) # N행 M열 입력.
board = [ list(input()) for _ in range(N) ] # 보드 완성.
res = sys.maxsize # 최솟값을 구해야 하므로 최댓값으로 설정. (최대가 64칸이므로 64로 해도 됨)

def search(x, y): # 8*8칸을 돌면서 (0, 0) 좌표가 흰색인 경우랑 검은색인 경우일 때 체스판과 틀린 경우를 카운팅.
    global res # 전역변수 선언
    arr = [row[y : y + 8] for row in board[x : x + 8]] # 보드칸 중에서 (x~x+8, y~y+8) 행렬만 따로 가져옴.
    color = ['W', 'B'] # 시작점(0, 0)이 흰색인 경우랑 검은색인 경우를 둘 다 서칭하기위해 선언.
    cnt = [0, 0] # 흰색인 경우랑 검은색인 경우의 틀린 횟수를 카운팅하기 위한 배열.
    for i in range(8):
        for j in range(8): # i행 j열일 때,
            # 체스판을 보면 (i + j)가 짝수인 경우랑 홀수인 경우는 각각 색깔이 같다. 이를 이용한다.
            # (i, j) 좌푯값이 원하는 색깔이 아닌 경우에 각각 cnt의 다른 요소를 +1 해준다.
            if arr[i][j] != color[(i + j) % 2]:
                cnt[0] += 1
            else:
                cnt[1] += 1
    res = min(res, *cnt) # 시작점이 흰색인 경우, 검은색인 경우, 기존의 최솟값 중에서 최솟값을 구해서 다시 최솟값을 설정.

for i in range(N-7): # 한번에 8칸씩 돌기 떄문에 전체 보드 행과 열의 -7 을 해준다.
    for j in range(M-7):
        search(i, j)

print(res)

 

처음에 N행 M열의 입력이 주어지는데, 최소 8*8이상의 보드판이 주어진다. 이중에 임의로 8*8칸을 골라서 그 칸들중에 체스판처럼 각 칸의 상하좌우가 다른 색이 아닌 경우의 수를 구하고, 그 수가 최소일 때를 출력하는 문제다. 

 

이단 모든 보드판을 돌아야 하므로 완전 탐색이고, 한번 서칭할 때 8*8씩 도므로 N-7, M-7 씩만 반복하면 된다. 

 

최솟값을 구하는 문제여서 res 에다가 최대 정수를 초기화 해두었는데 어차피 모든 칸수가 다를 경우는 32칸이므로 32라고 해도 되지만 그냥 습관상 넉넉히 주었다. (8*8칸이라 주석에는 64라고 했지만 시작점의 색깔이 다를 경우엔 0이 되므로 최대는 모두 같은 색인 경우인 32이다) 

 

search 함수에서는 시작좌표 x, y를 받아와서 보드칸의 (x~x+8, y~y+8) 부분만 떼어온다. 그리고 원래는 시작점이 흰색인 경우랑 검은색인 경우를 각각 나눠서 도는게 가독성 면에서는 좋겠지만,, 그냥 난 저렇게 흰색인 경우랑 검은색인 경우를 한번에 처리하도록 풀었다. 

 

	0	1	2	3
0	흰(0)	검(1)	흰(2)	검(3)
1	검(1)	흰(2)	검(3)	흰(4)
2	흰(2)	검(3)	흰(4)	검(5)
3	검(3)	흰(4)	검(5)	흰(6)

체스판을 보면 (i + j) 가 짝수일 때랑 홀수일 때는 같은 색인 걸 볼 수 있다. (왼쪽 아래의 대각선을 보면 됨)

 

반복문을 다 돌면 res 에다가 기존 res, 시작점인 흰색, 검은색일 때 틀린 횟수들 중 최솟값을 저장하고 최종적으로 res를 출력하도록 했다.