[프로그래머스] 게임 맵 최단거리 (with Python)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

풀이

최단거리 유형의 문제임을 확인하고 BFS를 이용하면 효과적으로 해결할 수 있다고 생각해서 BFS 알고리즘을 이용하여 문제를 풀었다.
최단거리를 구하려면 방문했던 곳은 다시 확인할 필요가 없기 때문에 visited를 선언해주고, visited가 False일 때에만 queue에 넣어줬다.
maps는 이전까지의 최단거리에 1을 더해주면서 갱신했고 최종적으로 n*m 크기의 맵에서 maps[n-1][m-1]까지의 최단거리는 maps[n-1][m-1]가 된다.

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

결과

[입출력 예 #1]

👉

maps[n-1][m-1]에 도달 가능하며 최단경로는 11이다. maps[1][4]에서 아래 방향인 maps[2][4]는 이미 방문했던 지점이기 때문에 큐에 넣지 않는다.


[입출력 예 #2]

👉

maps[n-1][m-1]에 도달 불가능하기 때문에 -1을 return 한다.