출처 : 파이썬 알고리즘 인터뷰

BFS를 깨부술 차례가 왔다.

DFS를 완전히 깨부쉈나??!는 잘 모르겠지만 그래도 전보다는 훨씬 많이 이해할 수 있게 되었다.

많은 걸 바라진 않아....BFS도 그렇게 조금씩 정복해보자

오늘의 문제

leetcode 743.Network Delay Time

모든 노드를 방문하는데 걸리는 시간을 반환하는 문제이다.

생각의 흐름

모든 노드를 방문하는 시간이면

• 어떤 노드 방문까지 제일 오래걸리는 시간이랑

• 모든 노드를 방문했는지

를 따져보면 되겠구나

-> 탐색 풀을 저장할 리스트와 탐색한 순서를 담을 리스트가 필요하겠군

탐색 풀을 저장할 리스트가 알아서 시간 순으로 정렬해주면 참 좋겠군

=> 우선순위 큐 이용하기

접근 0 : 다익스트라 알고리즘

노드 주변의 최단 경로를 택하는 그리디 알고리즘 중 하나로, 실행 속도 빠르고 BFS의 대표적 알고리즘

function Dijkstra(graph, source):
  dist[source] = 0
  
  create vertex priority queue Q
  
  for each vertex v in graph:
    if v != source:
      dist[v] = INFINITY
      prev[v] = UNDEFINED
      
    Q.add_with_priority(v, dist[v])
    
  while Q is not empty:
    u = Q.extract_min()
    for each neighbor v of u:
      alt = dist[v] + length(u,v)
      if alt < dist[v]:
        dist[v] = alt
        prev[v] = u
        Q.decrease_priority(v, alt)
        
  return dist, prev

접근 1

graph 화

graph = collections.defaultdict(list)

for u,v,w in times:
  graph[u].append((v,w))

접근 2

탐색 풀이 되어줄 우선순위 queue Q (시간, 노드) 와

탐색 경로와 시간을 담아줄 dist 정의 [노드, 시간] 형태

Q = [(0,K)]
dist = collections.defaultdict(int)

접근 3

Q에서 우선순위 pop해서 가장 가까운 거리 순으로 (탐색하지 않은 곳)탐색하기

while Q:
  time, node = heapq.heappop(Q)
  if node not in dist:
    alt = time + w
    heapq.heappush(Q, (alt, v))

접근 4

모두 방문했다 == N과 dist의 length가 같음

아니면 -1 반환

if len(dist) == n:
  return max(dist.values())

return -1

최종 코드

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
      graph = collections.defaultdict(list)
      
      for u,v,w in times:
        graph[u].append((v,w))
        
      Q = [(0,k)]
      dist = collections.defaultdict(int)
      
      while Q:
        time, node = heapq.heappop(Q)
        if node not in dist:
          for v,w in graph[node]:
            alt = time + w
            heapq.heappush(Q, (alt, v))
        
      if len(dist) == n:
        return max(dist.values())
      
      return -1

아 이해하는데 한참걸림 진짜 아오 어려워