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

📖 문제

📖 예제

📖 풀이

V, E = map(int, input().split())
line = [list(map(int, input().split())) for _ in range(E)]
Vroot = [i for i in range(V+1)]

line.sort(key=lambda x: x[2])

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

ans = 0
for s, e, w in line:
  eRoot = find(e)
  sRoot = find(s)
  if eRoot != sRoot:
    if eRoot < sRoot:
      Vroot[sRoot] = eRoot
    else:
      Vroot[eRoot] = sRoot
    ans += w

print(ans)

본 문제는 최소 스패닝 트리를 찾는 문제로 prim/kruskal 알고리즘으로 해결할 수 있다.
본 풀이는 kruskal 알고리즘의 코드를 활용한다.