[백준2211] / 네트워크 복구 - 다익스트라

 

백준2211

 

 

푼 날짜 : 2024.11.14

푼 문제 : [2211] / 네트워크 복구

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

다익스트라를 사용하여 최소비용을 계산한다.

최소비용을 계산하며 어디서 출발해서 어디로 연결되는지(연결되는 A, B)를 같이 저장했다.

이후 해당 연결된 A, B를 출력했다.

 

아래와 같은 예제를 살펴보면,

4 5
1 2 1
1 4 4
1 3 2
4 2 2
4 3 3

 

그래프는 아래와 같이 그려지며 최단 비용으로 연결하는 것은 노란색과 같다.

(내)이해를 돕기 위한 그림

 

 

코드 :

import sys
import heapq

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    graph[A].append((B, C))
    graph[B].append((A, C))

# cost, node
heap = [(0, 1)]
# 연결된 A, 연결된 B, 비용 저장을 위하여 튜플로 저장
dist = [(-1, -1, float("INF")) for _ in range(N+1)]

# 시작점 초기화
dist[1] = (0, 0, 0)

while heap:
    now_cost, now_line = heapq.heappop(heap)
    if dist[now_line][2] < now_cost: continue

    for next, cost in graph[now_line]:
        all_cost = now_cost + cost

        if dist[next][2] > all_cost:
        	# 연결된 A, 연결된 B, 비용 저장
            dist[next] = (now_line, next, all_cost)
            heapq.heappush(heap, (all_cost, next))

# 연결된 노드의 개수
print(len(dist[2:]))
# 순서대로 출력
for i, j, cost in dist[2:]: print(i, j)

 

 

오늘도 해치웠다!