프로그래머스 가장 먼 노드 코드 및 해설 (파이썬)

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

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

 

3가지 수정사항을 제외하고 다익스트라 알고리즘을 그대로 활용해 풀이했습니다.

(1) 간선이 양방향이므로 graph에 정보를 저장할 때 두 가지 방향을 모두 저장했습니다 

(2) 간선에 weight가 없으므로 일괄적으로 1로 통일했습니다 

(3) 마지막에 답을 반환할 때 1번 노드를 제외한, 2번에서 마지막 노드까지의 거리 중 최댓값을 구하고, 이 최댓값과 같은 거리를 갖는 노드의 개수를 반환하도록 했습니다

 

import heapq

def solution(n, edge):
    INF = int(1e9)
    graph = [[] for _ in range(n+1)]
    distance = [INF] * (n+1)
    
    # 간선 정보 저장하기 
    for e in edge:
        a, b = e
        # 양방향
        graph[a].append((b,1))
        graph[b].append((a,1))
    
    # 다익스트라 알고리즘 
    def dijkstra(start):
        q = []
        distance[start] = 0
        heapq.heappush(q, (0, start))
        
        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]))
    
    dijkstra(start=1)
    
    # 최대 거리 
    max_dist = max(distance[2:])
    # 최대 거리인 노드들의 개수 
    return len([d for d in distance if d == max_dist])