코딩테스트 가장 먼 노드 문제풀이

프로그래머스 가장 먼 노드(level 3) 문제풀이

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)
def solution(n, edge):
  q = []
  graph = [[] for _ in range(n+1)]
  distance = [INF]*(n+1)

  for i in range(len(edge)):
    graph[edge[i][0]].append((edge[i][1], 1))
    graph[edge[i][1]].append((edge[i][0], 1))
  heapq.heappush(q, (0, 1))
  distance[1] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      continue
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))
  tmp = 0
  cnt = 0
  for i in range(1, n+1):
    tmp = max(tmp, distance[i])
  for i in range(1, n+1):
    if distance[i] == tmp:
      cnt += 1

  return cnt

전형적인 다익스트라 문제로 다익스트라 알고리즘 자체가 어려워서 레벨 3인 것 같다.
우선순위 큐를 활용해서 다익스트라 코드를 쓰는 방법에 대해 공부가 됐고,

    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))

최단 거리 노드들 연결시키면서 퍼져나가는 방법에 대해 확실히 이해하는 계기가 됐다