부대복귀 BFS 예제 queue

 

from collections import deque


def solution(n, roads, sources, destination):
    graph = [[] for _ in range(n + 1)]
    for a, b in roads:
        graph[a].append(b)
        graph[b].append(a)

    # 거리 초기화
    distance = [-1] * (n + 1)
    distance[destination] = 0

    queue = deque([destination])

    # BFS
    while queue:
        current = queue.popleft()
        for next in graph[current]:
            if distance[next] == -1:
                distance[next] = distance[current] + 1
                queue.append(next)

    return [distance[s] for s in sources]

 

도착지에서 한 번만 BFS → 모든 노드까지 최단거리 한 번에 계산 (권장, O(N+M))

시작점마다 BFS → sources 개수만큼 반복 (최악 O(|sources|*(N+M)))

즉, 각 병사들이 도착지로 가는거 계산하는거보다
도착지에서 병사들한테로 퍼지는게 낫다

 

 

queue 쓰는 이유는 pop(0)이 O(n)인데 queue는 왼쪽, 오른쪽 둘다 O(1)걸림