12/19 게임 앱 최단거리

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

목표 지점까지 가는 최단거리를 구하는 문제이다..

현재 있는 지점을 queue에 계속해서 저장을 한다. 갈림길이 나왔을 때 지나가지 않은 길을 기억하기 위해 deque를 사용한다.

그리고 한칸씩 지나온 길마다 1씩 더해서 저장을 하면 현재까지 거쳐온 칸의 개수가 된다.

마지막에 queue가 비어있다면 모든 경우의 수를 다 거친 뒤이며 answer 값이 1이라면 마지막 좌표에 도달하지 못했다는 의미이다.

내 풀이

from collections import deque

def solution(maps):
    answer = 0
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    height, width = len(maps), len(maps[0])
    
    queue = deque()
    queue.append((0, 0))
    
    while queue :
        x, y = queue.popleft()
        for i in range(4) :
            cur_x = x + dx[i]
            cur_y = y + dy[i]
            if 0 <= cur_x < height and 0 <= cur_y < width and maps[cur_x][cur_y] == 1 :
                maps[cur_x][cur_y] = maps[x][y] + 1
                queue.append((cur_x, cur_y))
    answer = maps[height - 1][width - 1]          
    if answer == 1 :
        answer = -1
    return answer