[221130]プログラマー-ゲームマップ最短距離

と知る

質問する

私の答え

from collections import deque


def solution(maps):
    queue = deque()
    n, m = len(maps), len(maps[0])  # 맵의 크기 n,m
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]   # 방향 변수
    x, y = 0, 0     # 현재 위치

    time = [[0] * m for _ in range(n)]  # (0,0) 에서 해당 칸까지 시간

    queue.append((x, y))
    time[x][y] = 1
    while queue:
        x, y = queue.popleft()
        if x == n and y == m:  # 도착 시 종료
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 맵 안에 존재 하는 올바른 경로 인지
            if 0 <= nx < n and 0 <= ny < m:
                # 벽(0)이 아닌 길(1) + 방문 하지 않은 길
                if maps[nx][ny] == 1 and time[nx][ny] == 0:
                    queue.append((nx, ny))  #
                    # 기존 시간 + 1, 방문 시간 증가
                    time[nx][ny] = time[x][y] + 1
                    
    return time[n - 1][m - 1] if time[n - 1][m - 1] != 0 else -1

# time
# [[1, 0, 9, 10, 11],
# [2, 0, 8, 0, 10],
# [3, 0, 7, 8, 9],
# [4, 5, 6, 0, 10],
# [0, 0, 0, 0, 11]]