프로그래머스_게임 맵 최단거리

문제

풀이

이 문제는 DFS/BFS 를 알고 있다면 간단하게 풀 수 있는 문제이다.
1. 출발 지점부터 시작해 0이면 벽이므로 패스 1이면 길이므로 전에 지나온 길에 +1을 더한다.
2. 위 과정을 반복하면서 마지막 출구에서의 값을 출력한다.

풀이 코드

from collections import deque

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

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