[백준 1197번 파이썬] 최소 스패닝 트리(MST) 알고리즘

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

 

 

 

 

Prim 알고리즘

노드와 연결된곳을 가장 최소가 되는 가중치 순으로 탐색하는 알고리즘입니다.

따라서 다익스트라와 우선순위 큐가 사용되는데

for _ in range(M):
    A,B,C = map(int ,input().strip().split())
    graph[A].append([C,B])
    graph[B].append([C,A])

C가 가중치인데 이걸 앞에다 저장해줍니다. 왜냐?

뒤에서 heappop()을 해줄건데 이건 앞에 있는 값 기준으로 최소비용을 계산하기 때문입니다.

가중치를 뒤에 두는 선택을 하면 최소비용 계산이 아닌

숫자가 낮은 노드순으로 탐색을 하게됩니다.

 

cnt 변수를 사용하여 모든 노드 탐색이 완료되면 강제로 탈출하게 만들어주고

visited배열을 사용하여 탐색한 노드에 재방문을 하지 않게 해줍니다.

마지막으로 answer 변수를 사용하여 노드에 방문할때마다 값을 더해줘서 최소비용을 계산해줍니다.

import heapq
import sys
input = sys.stdin.readline


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

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

for _ in range(M):
    A,B,C = map(int ,input().strip().split())
    graph[A].append([C,B])
    graph[B].append([C,A])

#다익스트라
answer = 0
cnt = 0
q = [[0,1]] #1에서 출발할거임

while q: #q가 아무것도 없어질 때까지!
    if cnt == N:
        break
    weight,node = heapq.heappop(q) #최소비용을 꺼내줌
    if visited[node] == 0:
        visited[node] = 1
        cnt += 1
        answer += weight
        for nxt in graph[node]:
            heapq.heappush(q,nxt)
print(answer)

 

 

---

kruskal 알고리즘

크루스칼 알고리즘은 기본적으로 Union-find를 사용할줄 알아야합니다.

2024.08.06 - [1일 1알고리즘] - [백준 1717번 유니온 파인드 알고리즘] 집합의 표현 파이썬 풀이

[백준 1717번 유니온 파인드 알고리즘] 집합의 표현 파이썬 풀이

이 글에 유니온 파인드 알고리즘이 설명되어있으니 참고 바랍니다.

 

크루스칼 알고리즘은 기본적으로 모든 노드, 가중치를 배열에 저장한뒤

최소비용으로 탐색하면서 탐색할시에 find를 해줘서 같은 부모에 위치한지 확인해줍니다.

이 과정을 거치는 이유는 사이클을 발생하는것을 방지하고 중복을 감지할 수 있습니다.

 

import heapq
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().strip().split())
link = [list(map(int, input().strip().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 A, B, weight in link:
    A = _find(A)
    B = _find(B)

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

 

유니온 파인드의 약간의 연장선이기에 유니온파인드를 이해하셨다면 이 코드도 쉽게 이해하실거라 생각됩니다.