[프로그래머스] 파이썬 _ 가장먼 노드

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

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

문제유형 : 다익스트라

 

문제풀이 : 

• 1번노드를 시작으로하는 다익스트라 알고리즘을 수행한다.
• 이때 모든 간선의 비용을 1로보고 계산한다.
• 다익스트라가 끝났을때 최단거리 테이블에서 INF을 제외한, 가장큰 비용을 갖는 노드의 개수를 출력한다.

 

정답코드 :

# 1번노드를 출발지로하여 다익스트라 실행
# 모든 간선의 비용을 1로보고 다익스트라가 끝났을때 최단거리테이블에서 가장 값이 높은 노드를 출력한다.
import heapq
def solution(n, edge):
    answer = 0
    
    INF = int(1e9)
    
    distance = [ INF for _ in range(n+1) ]
    graph = [[] for _ in range(n+1)]
    
    
    for i in edge:
        a,b = i[0], i[1]
        graph[a].append(b)
        graph[b].append(a)
        
    dijkstra(1, distance, graph)
    
    cost = max(distance[1:])
    
    return distance.count(cost)
    
def dijkstra(start, distance, graph):
    q = []
    
    #거리, 노드
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        
        dist, curr = heapq.heappop(q)
        
        if distance[curr] < dist:
            continue
        
        for node in graph[curr]:
            cost = dist + 1
            if distance[node] > dist+1:
                distance[node] = dist+1
                heapq.heappush(q, (dist+1, node))