문제

게임 맵 최단거리

정답 코드

from collections import deque
dxs, dys = (1, -1, 0, 0), (0, 0, 1, -1)


def solution(maps):
    dq = deque()
    n, m = len(maps), len(maps[0])
    distance = [[n * m + 1 for _ in range(m)] for __ in range(n)]
    distance[0][0] = 1
    dq.appendleft((0, 0, 1))
    while dq:
        x, y, dis = dq.pop()
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and maps[ny][nx] and distance[ny][nx] > dis + 1:
                distance[ny][nx] = dis + 1
                dq.appendleft((nx, ny, dis + 1))
    return distance[n - 1][m - 1] if distance[n - 1][m - 1] != n * m + 1 else -1

풀이

BFS의 클래식 문제입니다!!
미로에서 거리 구하기 문제이죠

값을 넣고 빼는 자료구조는 리스트가 아니라 deque를 다음과 같은 이유로 사용했습니다

• stack이 아닌 양뱡향으로 값을 빼고 넣는 queue가 필요함
• 리스트는 값을 앞에서 빼고 넣을 경우 시간 복잡도가 좋지 않음

deque안의 값을 넣고 빼맨서 BFS를 활용해서 벽이 아니면서, 해당 칸까지 오는데 걸리는 최단 거리 배열보다 더 빠르게 오면 거리 배열을 갱신했습니다.

그리고 거리 배열의 우측 하단의 값이 초기값이면 도착을 못한 것이므로 -1, 초기값이 아니면 그 값을 리턴해줬습니다.

틀렸던 곳

• 정말 오랜만에 코테 문제를 풀어서 그런지 n, m이 같다고 가정하고 문제를 풀어서.... 30분을 날렸습니다ㅠㅠ 정답 코드 자체는 짜는데 이정도 안걸렸는데... 이 쉬운 문제에서 맞왜틀만 30분을 날렸습니다ㅠㅠ 문제를 똑바로 봅시다!!