프로그래머스: 가장 먼 노드

다익스트라 알고리즘을 사용한다.

참고: https://focalpoint.tistory.com/6

최단 거리 알고리즘

import heapq

def solution(n, edge):
    answer = 0
    max_dist = 0
    graph = [[] * (n+1) for _ in range(n+1)]
    for e in edge:
        u, v = e
        graph[u].append(v)
        graph[v].append(u)
    distance = [int(1e9)] * (n+1)
    pq = []
    heapq.heappush(pq, (0, 1))
    distance[1] = 0
    while pq:
        dist_u, u = heapq.heappop(pq)
        if dist_u > max_dist:
            answer = 1
            max_dist = dist_u
        elif dist_u == max_dist:
            answer += 1
        if distance[u] < dist_u:
            continue
        for v in graph[u]:
            if distance[v] > dist_u + 1:
                distance[v] = dist_u + 1
                heapq.heappush(pq, (distance[v], v))
    return answer