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

문제

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

소스코드

from collections import deque
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    visited = [[0] * (m) for _ in range(n)]
    
    q = deque()
    q.append([0,0,1])
    visited[0][0] = 1
    
    dx = [1,-1,0,0]
    dy =[0,0,1,-1]
    
    while q:
        x,y,cnt = q.popleft()
        if x == (n-1) and y == (m-1):
            return cnt

        for k in range(4):
            xx = x + dx[k]
            yy = y + dy[k]
            if 0<=xx<n and 0<=yy<m and maps[xx][yy]:
                if not visited[xx][yy]:
                    visited[xx][yy] = 1
                    q.append([xx,yy,cnt+1])

    return -1

설명

bfs로 (n-1,m-1) 에 도달할 수 있도록 탐색한다.

이때 좌표값과 좌표값을 이동할 때 마다 이동한 횟수 (cnt)를 함께 탐색해준다.