[Programmers | Level 2] 게임 맵 최단거리 (Python)

from collections import deque
dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]

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

bfs를 활용한 최단거리 구하기 문제

처음에 바보같이 dfs로 접근했다가 시간초과로 터졌다!

dfs는 최소를 보장해주지 않는다.