〔프로그래머스/파이썬〕게임 맵 최단거리(BFS)

출처

프로그래머스

 

---

 

풀이

from collections import deque

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

• 미로 문제로 전형적인 BFS 활용 문제
• collections 모듈로부터 deque 을 가져와서 사용하면 편하다