[백준] 1600번 말이 되고픈 원숭이 (Python)

백준 1600 말이 되고픈 원숭이

평범한 BFS 문제였지만 비슷한 실수를 반복해서 정리를 해야겠다고 다짐했다.

BFS를 활용해서 문제를 풀 때, 시작점이 도착점인 경우에 예외 처리를 까먹지 말자.

큐에서 꺼낸 값이 정답 값인지 확인할 경우에는 이런 과정이 필요가 없는 대신, 시간 복잡도가 늘어난다. 나는 반복문 내에서 정답 값을 찾는 것을 선호하기 때문에 예외 처리를 해야 한다.

import sys
from collections import deque

input = sys.stdin.readline

k = int(input().strip())
w, h = map(int, input().split())
if w == 1 and h == 1:
    print(0)
    exit(0)

isWall = [[False for _ in range(w)] for __ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

hdy = [1, 2, 2, 1, -1, -2, -2, -1]
hdx = [-2, -1, 1, 2, 2, 1, -1, -2]
dp = [[[True for _ in range(k + 1)] for _ in range(w)] for _ in range(h)]
for y in range(h):
    tmp = list(map(int, input().split()))
    for x in range(w):
        if tmp[x] == 1:
            isWall[y][x] = True

q = deque()
q.append([0, 0, k, 0])

while q:
    y, x, cnt, path = q.popleft()
    if cnt != 0:
        for d in range(8):
            tmpY = y + hdy[d]
            tmpX = x + hdx[d]
            if h > tmpY >= 0 and w > tmpX >= 0 and \
                dp[tmpY][tmpX][cnt - 1] and not isWall[tmpY][tmpX]:
                if tmpY == h - 1 and tmpX == w - 1:
                    print(path + 1)
                    exit(0)
                dp[tmpY][tmpX][cnt - 1] = False
                q.append([tmpY, tmpX, cnt - 1, path + 1])

    for d in range(4):
        tmpY = y + dy[d]
        tmpX = x + dx[d]
        if h > tmpY >= 0 and w > tmpX >= 0 and \
            dp[tmpY][tmpX][cnt] and not isWall[tmpY][tmpX]:
            if tmpY == h - 1 and tmpX == w - 1:
                print(path + 1)
                exit(0)
            dp[tmpY][tmpX][cnt] = False
            q.append([tmpY, tmpX, cnt, path + 1])
print(-1)