부대복귀.Py

from collections import deque, defaultdict

def bfs(nodes, start, end, visited, tables):
    visited.add(start)
    queue = deque([(start, 0)])
    while queue:
        node, cnt = queue.popleft()
        if node in end:
            tables[node] = cnt
        for _next in nodes[node]:
            if _next not in visited and _next in end:
                tables[_next] = cnt + 1
            if _next not in visited:
                visited.add(_next)
                queue.append((_next, cnt+1))
    return
    
def solution(n, roads, sources, destination):
    # 목적지 기준으로, 출발지까지의 거리를 역산하면 bfs로 한 번에 계산할 수 있어보인다.    
    nodes = defaultdict(set)
    for a, b in roads:
        nodes[a].add(b)
        nodes[b].add(a)
        
    visited = set()
    answer_table = defaultdict(lambda: -1)
    source_set = set(sources)
    bfs(nodes, destination, sources, visited, answer_table)
    
    answer = [answer_table[a] for a in sources]
    return answer