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

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

코딩테스트 연습 - 게임 맵 최단거리

from collections import deque

def solution(maps):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    n = len(maps)
    m = len(maps[0])
    visited = [[-1]*m for _ in range(n)]
    q = deque()
    q.append([0,0])
    visited[0][0] = 1
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and maps[nx][ny] == 1: # 벽이 없으면
                if visited[nx][ny] == -1: 
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx,ny])       
    return visited[-1][-1]

풀이

bfs 를 사용해서 푸는 간단한 풀이다.

다만, 최단경로의 최소값을 구해야되는데, 도달하지 못하면 -1을 리턴해야하니까

처음에 visited 방문처리 초기값을 평소 주던 0이 아닌 -1로 준다.