[그래프] 가장 먼 노드

INF = int(1e9)
import heapq

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

    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)

    #1 번부터 시작
    #거리 0으로
    start = 1
    distance[start] = 0
    #우선순위 큐에 첫 시작 점 넣는다
    q = []
    heapq.heappush(q,(0,start))
    #큐가 빌때까지
    while q:
        dist, x = heapq.heappop(q)
        #꺼내온것과 연결된것 탐방
        for i in graph[x]:
            #갔던곳이면 무시
            if dist > distance[i]:
                continue
            cost = dist + 1
            if distance[i] > cost:
                distance[i] = cost
                heapq.heappush(q,(cost,i))
    distance[0] = -1
    answer = distance.count(max(distance))
    return answer