[MST] 백준_1197

나의 풀이

import sys
input = sys.stdin.readline

V, E = map(int, input().split())
matrix = [[0]*V for _ in range(V)]

for _ in range(E):
  A, B, C = map(int, input().split())
  matrix[A-1][B-1] = C
  matrix[B-1][A-1] = C

if V == 1:  
  print(matrix[0][1])
  return

group = [0 for _ in range(V+1)]
included = 2
group[1] = 1
SOW = 0
min = sys.maxsize 
minIdx = sys.maxsize

for i, v in enumerate(matrix[0]):
  if v != 0 and v < min:
    minIdx = i
    min = v
    
group[minIdx+1] = 1
SOW += v

while True:
  if included==V: break
  
  min = sys.maxsize
  minIdx = sys.maxsize
  
  for idx in range(1, V+1):
    if group[idx] == 0:
      for i, v in enumerate(matrix[idx-1]):
        if group[i+1] == 0 and v < min:
          min = v
          minIdx = i
  group[minIdx+1] = 1
  included += 1
  SOW += min

print(SOW)

집합에 포함된 정점은 리스트에 넣는다.
집합에 안 포함되었으며 집합에 포함된 정점에서 1개 간선으로 갈 수 있는 경로가 있는 정점을 검사하며
하나씩 포함시킨다.
예전에 Prim알고리즘에 대해 배웠던 기억을 떠올려 일단 되는대로 코드를 짜보았다.
테스트코드와 내가 작성한 몇가지 테스트에 대해서는 에러없이 작동했지만 백준 사이트에서는 컴파일에러가 났다. 아무래도 Spanning Tree에 대해 다시 제대로 공부한 다음 풀어야겠다고 생각했다.

옳은 풀이(다른 사람의 풀이)

출처: https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html, https://hillier.tistory.com/54

Kruskal 알고리즘

import sys
input = sys.stdin.readline
 
V, E = map(int, input().split())
Vroot = [i for i in range(V+1)]
Elist = []
for _ in range(E):
    Elist.append(list(map(int, input().split())))
 
Elist.sort(key=lambda x: x[2])
 
 
def find(x):
    if x != Vroot[x]:
        Vroot[x] = find(Vroot[x])
    return Vroot[x]
 
 
answer = 0
for s, e, w in Elist:
    sRoot = find(s)
    eRoot = find(e)
    if sRoot != eRoot:
        if sRoot > eRoot:
            Vroot[sRoot] = eRoot
        else:
            Vroot[eRoot] = sRoot
        answer += w
 
print(answer)

Prim 알고리즘

import sys
import heapq
input = sys.stdin.readline
 
V, E = map(int, input().split())
visited = [False]*(V+1)
Elist = [[] for _ in range(V+1)]
heap = [[0, 1]]
for _ in range(E):
    s, e, w = map(int, input().split())
    Elist[s].append([w, e])
    Elist[e].append([w, s])
 
answer = 0
cnt = 0
while heap:
    if cnt == V:
        break
    w, s = heapq.heappop(heap)
    if not visited[s]:
        visited[s] = True
        answer += w
        cnt += 1
        for i in Elist[s]:
            heapq.heappush(heap, i)
 
print(answer)