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

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

BFS, 너비 우선 탐색이므로 가장 처음 방문했을 때 계산된 maps[][] 값이 최단 거리가 된다.

 

from collections import deque

def solution(maps):
    answer = -1
    n = len(maps)
    m = len(maps[0])
    visit = [[0 for j in range(m)] for i in range(n)]
    queue = deque([[0, 0]])
    visit[0][0] = 1
    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while queue:
        x, y = queue.popleft()
        
        for i in d:
            x_ = x + i[0]
            y_ = y + i[1]
            
            if x_ >= 0 and x_ < n and y_ >=0 and y_ < m and visit[x_][y_] == 0 and maps[x_][y_] == 1:
                visit[x_][y_] = 1
                maps[x_][y_] = maps[x_][y_] + maps[x][y]
                if x_ == n - 1 and y_ == m - 1:
                    answer = maps[x_][y_]
                    queue.clear()
                    break
                else:
                    queue.append([x_, y_])
            
    return answer

print(solution([[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