Level 3 가장 먼 노드 Python3

https://programmers.co.kr/learn/courses/30/lessons/49189?language=python3# 

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

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_가장먼노드.py

hwayeon351/Programmers-Algorithms

from collections import defaultdict
from heapq import heappop, heappush
def dijkstra(graph, start, distances):
    q = []
    heappush(q, [0, start])
    while q:
        cur_dis, cur_dest = heappop(q)
        if cur_dis > distances[cur_dest]: continue
        distances[cur_dest] = cur_dis
        for new_dest in graph[cur_dest]:
            dis = cur_dis + 1
            if dis < distances[new_dest]:
                distances[new_dest] = dis
                heappush(q, [dis, new_dest])
                
def solution(n, edge):
    distances = {node: float('inf') for node in range(1, n+1)}
    graph = defaultdict(set)
    for e in edge:
        graph[e[0]].add(e[1])
        graph[e[1]].add(e[0])
    dijkstra(graph, 1, distances)
    return list(distances.values()).count(max(distances.values()))

---

풀이 과정

풀이 시간 19분

그래프의 특정 노드에서 시작하여 다른 노드까지 가는 최단 경로를 구하기 위해 다익스트라 알고리즘을 적용할 수 있는 문제다.

출발 노드 -> 도착 노드로 다다르는 최단 경로를 구하기 위해서는 여러 경로들의 거리를 비교하여 작은 거리를 선택해야 한다.

이를 위해 Min Heap 자료구조를 활용할 수 있다. Heap에 [거리, 도착지]를 넣어줌으로써 출발 노드로부터 도착 노드까지 가장 적은 거리가 루트에 배치되기 때문이다.

먼저, 다익스트라 알고리즘의 결과인 출발지로부터 각각의 도착지까지의 거리를 담을 distances 딕셔너리를 생성한다.

힙을 통해 출발 노드로부터 다른 모든 도착 노드들까지 거리는 최소 거리 distances[도착지] 값을 갱신해 나가면 된다.

힙에서 pop할 때마다 출발지로부터 해당 도착지까지 걸리는 최소 거리를 이전 경로로 부터 저장된 distances[도착지] 값과 비교하여 작은 값으로 계속해서 distances[도착지] 값을 갱신하면 최종적으로 최단 경로를 구할 수 있다.

from collections import defaultdict
from heapq import heappop, heappush
def dijkstra(graph, start, distances):
    q = []
    #시작 노드를 Min heap에 push
    #거리 값을 기준으로 Min heap 구조를 구성
    heappush(q, [0, start])
    #heap이 빌 때까지 경로를 탐색
    while q:
        #heap의 루트가 정점 1로부터 가장 적은 거리에 있는 도착 노드
        cur_dis, cur_dest = heappop(q)
        #현재 도착 노드까지 더 적은 거리로 경로를 탐색한 경우 -> 더 탐색할 필요가 없음 continue
        if cur_dis > distances[cur_dest]: continue
        #현재 도착 노드까지의 최단 거리를 갱신한다
        distances[cur_dest] = cur_dis

        #현재 도착 노드를 경유하여 다른 도착 노드로 도달하는 경로를 탐색
        for new_dest in graph[cur_dest]:
            #모든 간선의 가중치 = 1
            dis = cur_dis + 1
            #현재 도착 노드를 경유하여 다른 도착 노드로 도달하는 거리가 이전 경로보다 작은 경우 distances를 갱신하고 힙에 push
            if dis < distances[new_dest]:
                distances[new_dest] = dis
                heappush(q, [dis, new_dest])
                
def solution(n, edge):
    #시작 노드로부터 도착 노드까지 걸리는 최소 거리를 담는 딕셔너리
    distances = {node: float('inf') for node in range(1, n+1)}
    #그래프 초기화
    graph = defaultdict(set)
    for e in edge:
        graph[e[0]].add(e[1])
        graph[e[1]].add(e[0])
    #시작 노드 = 1
    dijkstra(graph, 1, distances)
    return list(distances.values()).count(max(distances.values()))
#시간복잡도 = O(ElogV) 공간복잡도 = O(V)