[파이썬]백준 1018 체스판다시칠하기

링크

백준 1018 체스판다시칠하기

싸피 1학기 마지막 프로젝트에 집중하느라 그동안 1일 1알고리즘을 못하고있었다.
오늘부터 다시 마음을 다잡고 시작해야겠다.
물론 워밍업이 필요하니 비교적 쉬운문제를 풀었다.

완전탐색으로 해결했는데, 답이 되는 리스트를 미리 만들어 놓고 해당 리스트와 체스판을 비교하는 식으로 구현해 비교적 계산없이 간단하게 해결할 수 있었다.

바꿔야 하는 판을 계산하는 함수에도 가지치기를 하는 코드를 써서 속도를 줄일 수 있었다.

정답 코드

import sys; input = sys.stdin.readline

def check(r, c):
    global ans
    tmp1, tmp2 = 0, 0
    for i in range(8):
        for j in range(8):
            nr, nc = r + i, c + j
            if board[nr][nc] != sol1[i][j]:
                tmp1 += 1
            if board[nr][nc] != sol2[i][j]:
                tmp2 += 1
            # 가지치기
            if tmp1 >= ans and tmp2 >= ans:
                return
    ans = min(ans, tmp1, tmp2)

N, M = map(int, input().split())
board = [input() for _ in range(N)]
# 완성된 두가지 모양의 체스판
sol1 = ['WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW']
sol2 = ['BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB']
ans = 65

end_r = N - 8
end_c = M - 8

for i in range(end_r + 1):
    for j in range(end_c + 1):
        check(i, j)

print(ans)

알게된 것👨‍💻

• 1일 1알고리즘 다시시작!