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

이 문제는 최단거리를 찾는 것이라서 BFS로 푸는 것이 빠르다.

 

from collections import deque

def solution(maps):
    answer = 0
    
    n = len(maps)
    m = len(maps[0])
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    def bfs(X, Y):
        queue = deque()
        queue.append((X,Y))
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<= nx <= n-1 and 0 <= ny <= m-1 and maps[nx][ny] == 1:
                        queue.append((nx, ny))
                        maps[nx][ny] = maps[x][y] + 1
        return maps[n-1][m-1]
    result = bfs(0,0)
    if result == 1:
        return -1
    else:
        return result

map에 그대로 거리를 표시하고 maps[nx][ny] == 1로 비교함으로써 처음 방문한 것인지 그리고 장애물인지를 한번에 판단할 수 있다.