프로그래머스 Level 4 - 게임 맵 최단거리

문제

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

풀이 과정

BFS 를 통해 목표지점까지의 최단 거리를 탐색하는 문제이다.

방문여부와 거리 정보를 저장히기 위해서 딕셔너리 자료형을 사용할수도 있지만 게임맵과 동일한 이차원 배열을 선언해서

-1일 경우는 아직 방문하지 않은 지점, 그 외의 경우는 이미 방문해서 최단 경로를 구한 지점으로 판단하도록 했다.

이렇게 하면 트리 탐색시간을 절약할 수 있어서 더 빠른 수행시간을 가지게 된다.

코드

from collections import deque


dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(maps, start):
    N, M = len(maps), len(maps[0])
    q = deque()

    dist = [[-1 for _ in range(M)] for _ in range(N)]
    goal = (N-1, M-1)

    q.append(start)
    dist[start[0]][start[1]] = 1

    while q:
        here = q.popleft()
        if here[0] == goal[0] and here[1] == goal[1]:
            return dist[here[0]][here[1]]

        for i in range(4):
            next_x, next_y = here[0] + dx[i], here[1] + dy[i]
            if 0 <= next_x < N and 0 <= next_y < M:
                if maps[next_x][next_y] != 0 and dist[next_x][next_y] == -1:
                    dist[next_x][next_y] = dist[here[0]][here[1]] + 1
                    q.append((next_x, next_y))
    return -1


def solution(maps):
    answer = bfs(maps, (0, 0))
    return answer


maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]
print(solution(maps))