[백준] 1197번 최소 스패닝 트리

코드

# 크루스칼 알고리즘

import sys
input = sys.stdin.readline

def find(x, lst):
  if x != lst[x]:
    lst[x] = find(lst[x], lst)
  return lst[x]

def union(a,b,lst):
  a = find(a, lst)
  b = find(b, lst)
  if a < b:
    lst[b] = a
  else:
    lst[a] = b

n,m = map(int, input().split())

parent = [i for i in range(n+1)]
edge = []

for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((c,a,b))
edge.sort(key=lambda x: x[0]) # 비용을 오름차순으로 정렬

res = 0
for i in range(m):
  cost, v1, v2 = edge[i]
  if find(v1, parent) != find(v2, parent): # 루트 노드가 같지 않으면
    union(v1,v2,parent) # 합쳐준다
    res += cost
print(res)

서로소 집합을 이용하는 크루스칼 알고리즘이다.

 

코드2

# 프림 알고리즘
# 다익스트라와 구분

import sys, heapq

input = sys.stdin.readline
n,m= map(int, input().split())

graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)

for _ in range(m):
  a,b,c = map(int, input().split())
  graph[a].append((c,b)) # 비용을 앞에 넣어준다.
  graph[b].append((c,a))

def prim():
  total = 0
  queue = [(0,1)] # 프림 알고리즘은 시작점이 어디든 상관 없다.
  while queue:
    weight, node = heapq.heappop(queue)
    if not visited[node]:
      total += weight
      visited[node] = True
      for i in graph[node]:
        heapq.heappush(queue,(i[0],i[1]))
  return total
print(prim())

위 알고리즘은 정점과의 관계를 통해 최소 신장 트리를 찾는 프림 알고리즘이다. 정점을 찾는 자료구조에 따라 성능에 영향을 받는다.