1 minute read

문제

접근 방법

처음에는 가중치 정보들을 모두 heap에 넣고 제일 작은 가중치 정보를 하나씩 가져와 최소 스패닝 트리를 구성하려고 했다. 하지만 최소 스패닝 트리가 되기 위해서는 cycle이 존재하면 안 되기 때문에 오답이었다. 최소 스패닝 트리를 찾는 알고리즘을 두 가지를 찾았다.

1. 프림 알고리즘

프림 알고리즘은 임의의 한 정점에서 시작하여, 현재 트리에 포함된 정점들과 연결된 간선 중 가장 가중치가 낮은 것을 선택해 트리를 점차 확장해 나간다. 이 과정을 모든 정점이 트리에 포함될 때까지 반복한다.

정답 코드


import sys
import heapq
input = sys.stdin.readline

v,e = map(int, input().split())

"""
크루스칼 알고리즘: ElogE
프림 알고리즘: VlogV + ElogE
"""

visited = set()
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a,b,c = map(int, input().split())
    graph[a].append((c,a,b))
    graph[b].append((c,b,a))

#임의의 시작점
start = 1
#그 시작점으로부터 연결된 간선 정보들 heapify
nodes = graph[1][:]
heapq.heapify(nodes)
visited.add(1)
total_w = 0

while nodes:
    weight, from_, to_ = heapq.heappop(nodes)
    if to_ in visited:
        continue
    visited.add(to_)
    total_w += weight
    for new_w, a, b in graph[to_]:
        if b not in visited:
            heapq.heappush(nodes, (new_w, a, b))
print(total_w)

2. 크루스칼 알고리즘

크루스칼 알고리즘은 간선 정보들 중 가장 작은 가중치를 가진 간선을 하나씩 선택하면서 기존의 그래프와 합치는 것이다. 이때, 선택한 간선으로 인해 cycle이 생긴다면, 그 간선은 제외하는 방법으로 spanning tree의 특성을 유지한다.

정답 코드 (크루스칼 알고리즘)

import sys
import heapq
input = sys.stdin.readline

v,e = map(int, input().split())
nodes = []
"""
크루스칼 알고리즘: ElogE
프림 알고리즘: VlogV + ElogE
"""
def find(parent, node):
    if parent[node] != node:
        parent[node] = find(parent, parent[node])
    return parent[node]


def union(parent, a, b, rank):
    a = find(parent, a)
    b = find(parent, b)
    if rank[a] > rank[b]:
        parent[b] = a
    elif rank[b] > rank[a]:
        parent[a] = b
    else:
        parent[a] = b
        rank[b] += 1

for _ in range(e):
    a,b,c = map(int, input().split())
    heapq.heappush(nodes, (c,a,b))

total = 0
rank = [0]*(v+1)
parent = [i for i in range(v+1)]
while nodes:
    w, a, b = heapq.heappop(nodes)
    if find(parent, a) != find(parent, b):
        #사이클 형성하지 않는다면 합치기
        union(parent, a, b, rank)
        total += w

    
print(total)

You May Also Enjoy