백준 1197. 최소 스패닝 트리

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

1. 프림

# 프림 풀이(다익스트라)

import heapq
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
arr = [[] for _ in range(N+1)]
visited = [ 0 for _ in range(N+1)]

for _ in range(M):
    A,B,C = map(int,input().split())

    arr[A].append([C,B]) # 가중치를 기준으로 push, pop을 해줘야하니까 순서를 바꾸기
    arr[B].append([C,A])

ans = 0
cnt = 0

q = [[0,1]] # 1에서 출발할거다! 가중치 없이!

while q:

    if cnt == N: # 모든 정점을 방문했다면? = 모든 정점이 연결됐다면
        break

    weight,node = heapq.heappop(q) # 최소비용 꺼내주기

    if visited[node] == 0:
        visited[node] = 1
        ans += weight
        cnt += 1

        for nxt in arr[node]:
            heapq.heappush(q,nxt) # 담아주기

print(ans)

2. 크루스칼 풀이(최적화된 유니온파인드) -> 1보다 메모리는 더 많이 사용하지만 시간은 절반

# 크루스칼 풀이(유니온파인드)

# 1. 모든 링크를 한번에 가져온다.
# 2. 링크를 연결하면서 같은 집합으로 만들어준다.
# 3. 만약에 이미 같은 집합이라면 연결하지 않는다.

# union 최적화!

import sys
input = sys.stdin.readline

def _find(x):
    while par[x] != x:
        x = par[x]
    return x

def _union(a, b):
    a = _find(a)
    b = _find(b)

    if a == b:
        return

    if rank[a] < rank[b]:
        par[a] = b
    elif rank[b] < rank[a]:
        par[b] = a
    else:
        par[a] = b
        rank[b] += 1

N, M = map(int,input().split())
link = [list(map(int,input().split())) for _ in range(M)]
link.sort(key=lambda x:x[2]) # 가중치 기준으로 정렬

par = [i for i in range(1_000_001)]
rank = [0 for _ in range(1_000_001)]

ans = 0

for i in range(M):
    A = link[i][0]
    B = link[i][1]
    weight = link[i][2]

    A = _find(A)
    B = _find(B)

    if A == B:
        continue
    else:
        _union(A,B)
        ans += weight

print(ans)