[코테] BFS - 게임 맵 최단거리[프로그래머스]

문제:

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

입력:
maps:	                                                       answer:
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	    11
[[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]]	    -1

풀이:

BFS 문제의 대표격인 길찾기 문제다.
범위를 방문할 수 있는 가장 가까운 거리부터 시작해서 최종 도착지까지 넓혀가며, 최종 도착지까지 갈 수 있다면 가장 최단거리로 갈 수 있는 길이를 구하고 도착할 수 없는 경우라면 -1을 리턴한다.

1. 한 번 방문한 곳은 다시 방문하지 않도록 방문한 것을 체크할 체크 배열을 만들 수 있고, 아니면 주어진 maps는 0과 1로만 이루어져 있기에 maps 자체에서 거리를 업데이트 해도 무방하다.
2. 최종 도착지점에 도착했을 시 더 이상 탐색하지 않도록 최종 도착지점의 이동거리를 바로 출력하고 함수를 종료시킨다.

코드:

from collections import deque
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    dx = [0, 1, 0, -1]
    dy = [-1, 0 , 1, 0]
    dQ = deque()
    dQ.append((0, 0))
        
    while dQ:
        x, y = dQ.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                dQ.append((nx, ny))
                if maps[n-1][m-1] > 1:
                    return maps[n-1][m-1]
                
    if maps[n-1][m-1] <= 1:
        return -1
        
    return maps[n-1][m-1] # 사실 이 부분까지 내려오지 않는다.

예시:
maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]
print(solution(maps)) # 11

maps1 = [[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(maps1)) # -1

maps2 = [[1, 1]]
print(solution(maps2)) # 2