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

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

프로그래머스

풀이

간단한 최단거리 문제다. 원래는 이동할때마다 원래 칸에서 +1해서 map에 저장하면서 풀수도 있지만, 나는 cnt를 패러미터로 구하는게 더 편해서 cnt를 패러미터로 넣어주고 만약 n-1, m-1에 다다르면 break해주는 식으로 해주었다.

from collections import deque
def solution(maps):
    answer = -1
    visited = [[False for _ in range(len(maps[0]))]for _ in range(len(maps))]
    q = deque()
    q.append([0, 0, 1])
    visited[0][0] = True
    flag = False
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while q:
        x, y, cnt = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= len(maps) or ny >= len(maps[0]):
                continue
            if visited[nx][ny]:
                continue
            if nx == len(maps)-1 and ny == len(maps[0])-1:
                flag = True
                answer = cnt+1
                break
            if maps[nx][ny] == 1:
                q.append([nx, ny, cnt+1])
                visited[nx][ny] = True
        if flag:
            break
    return answer