[프로그래머스] Level3 가장 먼 노드(python)

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

1. 내가 작성한 코드

 

다익스트라를 이용해서 문제를 해결했다.

 

양방향 간선이라서 graph[i[0]]과 graph[i[1]]에게 서로의 정점을 넣어주고,

다익스트라 알고리즘을 이용해서 문제를 해결하면 된다.

 

import heapq
INF = int(1e9)

def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    distance = [INF] * (n+1)
    
    for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
        
    q = []
    distance[1] = 0
    heapq.heappush(q,(0,1))

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

    check = max(distance[1:])
    
    return distance.count(check)