프로그래머스 코딩테스트 고득점 Kit_그래프_가장 먼 노드

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

그래프를 인접리스트 형태로 표현한다.

파이썬의 heapq모듈을 사용하여 최솟값을 항상 pop한다.
거리가 최소인 값을 pop하고 해당 노드를 방문한 적이 없다면 딕셔너리 path에 노드:최단거리 를 추가하고 해당 노드와 인접한 노드들을 거리와 함께 q에 추가한다.

딕셔너리 path에 모든 노드들에 대한 최단경로가 존재한다면, 최단경로의 최대값의 개수를 반환한다.

구현 코드👇

from collections import defaultdict
import heapq
def solution(n, edge):
    answer = 0
    
    #그래프를 인접리스트로 표현
    graph = defaultdict(list)
    for v1, v2 in edge:
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    #q = [(거리, 노드), ...] / path = { 노드: 1부터 노드까지의 최단거리, ... }
    q, path = [(0, 1)], {}
    while 1:
        dist, node = heapq.heappop(q)
        if node not in path: #아직 최단거리를 구하지 않았을 경우
            path[node] = dist #최단거리 추가
            for v in graph[node]:
                heapq.heappush(q, (dist + 1, v))
        if len(path) == n: #모든 노드에 대하여 최단경로를 구하면
            dist_list = list(path.values()) 
            return dist_list.count(dist_list[-1]) #최대값의 개수 count하여 반환