알고리즘 고득점 Kit - BFS - 게임 맵 최단거리

문제 풀이

전형적인 BFS를 활용한 미로 탈출 문제입니다.
이런 미로 문제는 델타와 deque를 사용해서 popleft를 하며 이미 지나온 길은 지나치고 새로운 길만 찾아가면 됩니다

1. n, m은 미로의 크기지만 사람 기준으로 5X5라고 되어 있기에 n-1, m-1이라고 생각

2. visited 배열을 새로 만들어서 이미 지나온 길인지 확인

3. 리스트에서 계속 뽑아오며 델타를 활용해 갈 수 있는 길을 deque에 cnt(몇 번 움직였는지) 정보와 함께 넣어줌

4. 만약 y == n-1, x == m-1 인 경우 cnt를 바로 반환(BFS에서는 가장 먼저 도착하는 경우가 제일 짧은 경로임)

5. 심화 - 만약 가중치가 있는 맵인 경우에는 모든 도착 경우의 수를 따져봐야 하지만 해당 문제는 무조건 1이라 스킵

from collections import deque

def solution(maps):
    n, m = len(maps[0]), len(maps)
    visited = [[False] * n for _ in range(m)]
    visited[0][0] = True

    delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = deque([])
    q.append((1, 0, 0))

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

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

        for dy, dx in delta:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m and visited[ny][nx] == False and maps[ny][nx] == 1:
                q.append((cnt+1, ny, nx))
                visited[ny][nx] = True

    return -1