백준 2211 네트워크 복구 파이썬

🔗 백준 2211 네트워크 복구 

 

📌오늘의 학습 키워드

• 다익스트라 알고리즘

✨공부한 내용 본인의 언어로 정리하기

• 문제를 읽고 다익스트라 알고리즘을 생각하는 것까지는 했다.
• 벨만-포드 알고리즘을 풀었었기 때문에 다익스트라 알고리즘을 구현할 수 있다고 생각했으나, 거리 뿐만 아니라 어떤 간선을 사용했는 지까지 출력해야 해서 비효율적으로 짰더니 시간 초과가 났다. 
• 문명의 도움을 받아 효율을 높히기 위해서는 아래와 같이 해야한다는 것을 알았다.  
  1. deque가 아니라 heapqueue를 사용해야 함
  2. 모든 간선을 각 순환마다 도는 것이 아닌(이건 벨만 포드), 그 정점과 연결된 간선들만 탐색해야 함
• 사용한 자료구조
  • pq: heapqueue    # 정점 탐색 용
  • graph: [ (), () ] tuple array  # 각 정점에 어떤 간선+시간 이 걸리는 지 미리 기록
  • prev: [ ] int array    # 각 정점이 다익스트라 이후에 어떤 정점과 연결되어 있는 지 파악하는 용도
  • distance: [ ] int array      # 각 정점과 1 과의 거리

📚오늘의 회고

• 간선까지 구하라는 조건이 하나만 더 추가되어도 자료구조를 선택하는 데 애를 먹는 내 자신을 발견했다. 더 연습해야겠다.
• Trie에서 Class를 만들어 해결했기 때문에 그것을 써보려고 했는데 

max_dists = [DistanceNode()] * (N + 1)

for dist in max_dists:
    print(dist.info, dist.distance)

max_dists[1].distance = 0

이같은 상황에서 max_dists[1]만 초기화 해줬다고 생각했지만 전체가 초기화되는 것이다...! 

얕은 복사 때문에 발생한 문제로 

max_dists = [DistanceNode() for _ in range(N + 1)]

이렇게 해줘야 한다. 이게 그냥 상수면 상관이 없는데 참조형이라서 생기는 문제였다.

• 주말에 한주간 풀었던 문제들을 복습해야겠다. 🥹

 

[🤓문제 해결 코드]

import heapq
import sys
from collections import deque


N, M = list(map(int, input().split()))
dists = [list(map(int, input().split())) for _ in range(M)]


# 정보 미리 Graph 에 넣어두기
graph = [[] for _ in range(N + 1)]
for a, b, c in dists:
    graph[a].append((b, c))
    graph[b].append((a, c))

def dijkstra(start):
    distance = [sys.maxsize] * (N + 1)
    distance[start] = 0

    # 해당 노드가 무엇이랑 연결되어 있는지 추적하기 위해
    prev = [-1] * (N + 1)
    pq = []
    heapq.heappush(pq, (start, 0)) # (node, distance)

    while pq:
        node, dist = heapq.heappop(pq)

        if dist > distance[node]:
            continue

        for next, value in graph[node]:
            new_dist = dist + value
            if new_dist < distance[next]:
                distance[next] = new_dist
                prev[next] = node
                heapq.heappush(pq, (next, new_dist))
    return distance, prev

distance, prev = dijkstra(1)

result = []
for i in range(2, N + 1):
    if prev[i] != -1:
        result.append((prev[i], i))

print(len(result))
for a, b in result:
    print(a, b)