부대복귀 - Python, BFS

 

 

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

프로그래머스

 

 

코드 & 풀이

 

from collections import deque

def solution(n, roads, sources, destination):
    graph = [[] for _ in range(n + 1)]
    for start, end in roads:
        graph[start].append(end)
        graph[end].append(start)
    
    distances = [-1] * (n + 1)
    distances[destination] = 0
    
    que = deque([destination])
    
    while que:
        now = que.popleft()
        
        for nxt in graph[now]:
            if distances[nxt] == -1:
                distances[nxt] = distances[now] + 1
                que.append(nxt)
    
    return [distances[i] for i in sources]

 

 

노드별 거리가 무조건 1이기에 그냥 bfs로 함

 

근데 출발지마다 bfs 돌면 중복 계산되니까 (처음에는 각각했음)

 

그냥 도착지에서 bfs를 돌아서 각 지점별 도달거리를 측정해서 반환했음

 

 

 

 

다음에 또 봐요