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

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

일반적인 BFS 문제
시작점까지 포함한 최단거리를 계산하므로 visited[n-1][m-1]에 계산된 값을 return 해주면 최단거리가 된다
만약 visited[n-1][m-1]이 0이라면 주변이 모두 벽이라 접근할 수 없는 것이므로 -1을 return 해준다

from collections import deque
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    visited = [[0 for _ in range(m)] for _ in range(n)]
    
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    q = deque()
    q.append((0,0))
    visited[0][0] = 1   #시작점부터 거리 세기
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0<=nx<n and 0<=ny<m:
                if maps[nx][ny]==1 and visited[nx][ny]==0:
                    visited[nx][ny] = visited[x][y]+1
                    q.append((nx,ny))
                        
    if visited[n-1][m-1]:
        answer = visited[n-1][m-1]
    else:
        answer = -1
    
    return answer