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

기본 아이디어

• bfs

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    ax = [-1, 0, 1, 0]
    ay = [0, 1, 0, -1]

    queue = deque([(0, 0, 1)])
    visited = set()
    visited.add((0, 0))

    while queue:
        x, y, cnt = queue.popleft()

        if x == n - 1 and y == m - 1:
            return cnt

        for dx, dy in zip(ax, ay):
            nx, ny = x + dx, y + dy

            if 0 <= nx < n and 0 <= ny < m:
                if (nx, ny) not in visited and maps[nx][ny] == 1:
                    visited.add((nx, ny))
                    queue.append((nx, ny, cnt + 1))

    return -1

• bfs가 거리 순서대로 방문하기 때문에 따로 minum계산해주지 않아도 최단거리가 보장됨