Skip to main content

1844 - 게임 맵 최단거리

info

풀이 키워드​

스포주의

bfs


풀이 코드​

info
  • 메모리: 9400 KB
  • 시간: 10 ms
from collections import deque

dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    q = deque()
    q.append((0, 0, 1))
    maps[0][0] = 0
    while q:
        y, x, k = q.popleft()
        
        if y == n-1 and x == m-1:
            return k
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < m and maps[ny][nx]:
                maps[ny][nx] = 0
                q.append((ny, nx, k+1))
                
    return -1

풀이 해설​

큐를 이용해서 최단 거리를 탐색했다.

방문 처리는 visited를 따로 두지 않고, 기존 maps를 0으로 칠했다.


caution

방문 처리는 반드시 큐에 넣기 전에!​

큐에서 꺼내서 방문 처리할 땐 이미 다른 지점에서 중복 방문이 발생하므로 늦어버린다.

이는 효율성 통과에서 무조건 썰리게 되어있으므로, 꼭 큐에 넣기 전에 방문 처리해주자.


메모​

  • bfs 기초 문제임.
  • pop이랑 popleft랑 헷갈리지 마세요 둘이 방향 달라요........