[BOJ] Python 백준 네트워크 복구(2211)

https://www.acmicpc.net/problem/2211

 

다익스트라를 통한 최단경로 갱신 가능 여부를 보는 문제이다.

 

다익스트라의 시작점인 1부터 탐색을 진행한다.

heapq를 통해 비용과 시작점을 추가하고, 다익스트라를 진행합니다

이때 최소거리로 갱신되는 경우에만 parent 배열에 그 자리를 갱신합니다.

import sys
input = sys.stdin.readline
import heapq

N,M = map(int,input().split())

graph = [[] for _ in range(N+1)]
distance = [float('inf')] * (N+1)
parent = [0]*(N+1)
for _ in range(M):
    A,B,C = map(int,input().split())
    graph[A].append((B,C))
    graph[B].append((A,C))

def dijkstra(start):

    hq = []
    distance[start] = 0
    heapq.heappush(hq,(0,start))

    while hq:
        cost, now = heapq.heappop(hq)

        if distance[now] < cost:
            continue

        for next, dist in graph[now]:

            if distance[next] > cost+dist:
                parent[next] = now

                distance[next] = cost+dist
                heapq.heappush(hq,(cost+dist, next))


dijkstra(1)

count = 0
for i in distance:
    if i != 0 and i != float('inf'):
        count += 1

print(count)
for i in range(2, N + 1):
    print(parent[i],i)

 

 

회고.

parent 배열에 갱신하는 방법을 그냥 print하는 방식으로 진행했다 그러니 중복되는 값이 발생했다...

parent 배열을 사용하는 방법으로 문제를 푸는 방법을 시간내에 고안할 수 있어야 할것 같다,,, 아직 많이 부족하다...