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

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

프로그래머스

from collections import deque

def solution(maps):
    n = len(maps[0])  # 열의 크기
    m = len(maps)  # 행의 크기
    visited = [[0] * n for _ in range(m)]  # n x m 크기의 방문 배열
    
    def bfs(start):
        q = deque([start])
        visited[start[0]][start[1]] = 1  # 시작점 방문 처리
        
        while q:
            x, y = q.popleft()
            
            # 네 방향으로 이동
            for dx, dy in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                nx, ny = x + dx, y + dy
                # 맵 내부에 있는지 확인 & 방문 여부 확인 & 이동 가능 여부 확인
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and maps[nx][ny] == 1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx, ny])
                    # 도착 지점에 도달했으면 결과 반환
                    if nx == m - 1 and ny == n - 1:
                        return visited[nx][ny]
        return -1  # 도달할 수 없는 경우

    return bfs([0, 0])  # 시작점은 (0, 0)에서 시작