[Programmers | Level 3] 가장 먼 노드 (Python)

 

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)


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

    for i in edge:
        graph[i[0]].append((i[1], 1))
        graph[i[1]].append((i[0], 1))

    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 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]))

    max_dist = max(distance[1:])

    return distance.count(max_dist)

다익스트라 알고리즘을 활용하여 가장 멀리 있는 노드들의 개수를 리턴하는 문제.

heapq를 사용하여 시간 복잡도를 O(ElogV)로 단축시키는 것이 중요하다.

다익스트라가 요즘 코테에 많이 나오는 것 같아서 별표 다섯개 ! ⭐⭐⭐⭐⭐