[백준] 1600 말이 되고픈 원숭이 (파이썬 python)

 

 

문제 링크

 

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

1600번: 말이 되고픈 원숭이

 

 

문제 풀이

 

from collections import deque

def bfs():
    q = deque()
    q.append([0, 0, k])
    visited[0][0][k] = 0
    while q:
        x, y, z = q.popleft()
        if x == h - 1 and y == w - 1:
            return visited[x][y][z]
        if z > 0:
            for hdir in range(8):
                nx, ny = x + hdx[hdir], y + hdy[hdir]
                if 0 <= nx < h and 0 <= ny < w:
                    if visited[nx][ny][z - 1] == -1 and graph[nx][ny] == 0:
                        q.append([nx, ny, z - 1])
                        visited[nx][ny][z - 1] = visited[x][y][z] + 1
        for dir in range(4):
            nx, ny, = x + dx[dir], y + dy[dir]
            if 0 <= nx < h and 0 <= ny < w:
                if visited[nx][ny][z] == -1 and graph[nx][ny] == 0:
                    q.append([nx, ny, z])
                    visited[nx][ny][z] = visited[x][y][z] + 1
    return -1


k = int(input())
w, h = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(h)]
visited = [[[-1] * (k + 1) for _ in range(w)] for _ in range(h)]
hdx = [-2, -2, -1, -1, 1, 1, 2, 2]
hdy = [-1, 1, -2, 2, -2, 2, -1, 1]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
print(bfs())

 

 

이전에 풀었던 벽 부수고 이동하기2와 매우 비슷한 맥락의 문제로 빠르게 해결할 수 있었습니다.

k를 포함하여 거리 갱신과 방문 처리를 진행할 visited 배열을 만들어준 후,

말의 이동방향으로는 k를 모두 소진할 때까지 큐에 추가, 동서남북 방향으로는 모두 추가

이렇게 이동해나가며 (h - 1, w - 1)에 도달하면 거리값을 반환해줍니다.

큐에 대한 모든 값이 pop되었음에도 목표지점에 도달하지 못하면 -1을 반환해줍니다.