[프로그래머스][BFS][역발상] 부대복귀

부대복귀

프로그래머스

 

 

• 내 풀이 
  • 여러 출발점에서 각각 최단 경로를 찾으면, 출발점마다 dijkstra 수행해야 하므로 매우 비효율적
    
    • O((V+E)*V)
  • 도착지는 동일한데 각각의 출발점과의 거리를 찾는 것
    • ⇒ 도착지를 시작점으로 다른 지점까지의 거리를 찾으면 한번만 돌면됨

from collections import defaultdict
import heapq

def solution(n, roads, sources, destination):
    answer = []
    graph=defaultdict(list)
    
    for road in roads:
        s,e=road
        graph[s].append(e)
        graph[e].append(s)
    
    def bfs(start):
        queue=[]
        heapq.heappush(queue,(0,start))
        visited[start]=0
        
        while queue:
            d,cur=heapq.heappop(queue)
            
            for nxt in graph[cur]:
                if visited[nxt]<=d+1:
                    continue
                visited[nxt]=d+1
                heapq.heappush(queue,(d+1,nxt))
        
        return
    
    visited=[float('inf') for _ in range(n+1)]
    bfs(destination)
    for source in sources:
        answer.append(visited[source] if visited[source]!=float('inf') else -1)
    
    return answer