부대복귀

https://school.programmers.co.kr/learn/courses/30/lessons/132266

destination에서 출발해서 각각의 부대로 도착하는 거리를 측정하는 것이 더 쉽다.

최단 거리이므로 너비 우선 탐색을 응용하면 된다.    

from collections import defaultdict, deque


def solution(n: int, roads: list, sources: list, destination: int):
    graph = defaultdict(set)
    for v1, v2 in roads:
        graph[v1].add(v2)
        graph[v2].add(v1)
    visited = {}
    queue = deque()  # queue = deque([(destination, 0)])
    queue.append((destination, 0))
    while queue:
        node, distance = queue.popleft()
        if node not in visited:
            visited[node] = distance
            for each in graph[node]:
                queue.append((each, distance + 1))
    return [visited.get(each, -1) for each in sources]