99클럽 코테 스터디 5기 3일차 TIL + 다익스트라

-  오늘의 학습 키워드

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

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

import sys
import heapq
input = sys.stdin.readline

INF = int(1e9)

def dijkstra(start) :
    distance = [INF] * n
    distance[start] = 0
    pq = []
    pq.append((0,start))
    root = [-1] * n

    while pq :
        near_dist, near_node = heapq.heappop(pq)

        if near_dist > distance[near_node] :
            continue

        for i in arr[near_node] :
            dist = i[1] + near_dist
            if dist < distance[i[0]] :
                distance[i[0]] = dist
                heapq.heappush(pq,(dist,i[0]))
                root[i[0]] = near_node
    return root

n,m = map(int,input().split())
arr = [[] for _ in range(n)]
for _ in range(m) :
    a,b,c = map(int,input().split())
    arr[a-1].append((b-1,c))
    arr[b-1].append((a-1,c))

root = dijkstra(0)

connections = []

for i in range(1,n) :
    if root[i] != -1 :
        connections.append((root[i]+1, i+1))

print(len(connections))
for i in connections :
    print(i[0], i[1])

# 133620	248

- 오늘의 회고

1. 어떤 문제가 있었고, 나는 어떤 시도를 했는지

우선 이 문제는 다익스트라 문제였습니다. 다익스트라문제에 대한 개념과 원리는 정확히 알고 있었지만, 연결 노드를 기록할 방법을 어떻게 해야 하나가 고민이었습니다. 

2. 어떻게 해결했는지

노드를 기록할 수 있는 n 만큼의 길이의 root 리스트를 만들었습니다. 

3. 무엇을 새롭게 알았는지

다익스트라 응용 유형에 대해 알 게 되었습니다. 다음에 이런 비슷한 유형이 생기면 이런 방식으로 기록하여 해결하는 방안으로 하겠습니다.