[Dijkstra] 프로그래머스 L3 '가장 먼 노드' (Python)

<문제 링크>

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

코딩테스트 연습 - 가장 먼 노드

---

<문제 풀이>

1. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구해야 하므로 다익스트라 알고리즘을 이용
2. 간선은 양방향이므로 그래프에 노드를 서로 추가
3. 가장 멀리 떨어진 노드를 구해야 하므로 max() 메서드 이용

<코드>

import heapq

def dijkstra(start,distance,graph):
    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]))
                
def solution(n, edge):
    answer = 0
    distance = [int(1e9)] * (n+1)
    graph = [[] for _ in range(n+1)]
    
    for i in edge:
        graph[i[0]].append((i[1],1))
        graph[i[1]].append((i[0],1))
        
    dijkstra(1,distance,graph)
    
    distance.pop(0)
    for i in distance:
        if i==max(distance):
            answer += 1
            
    return answer