https://www.acmicpc.net/problem/1197
한 점에서 나머지 각 정점 까지의 최단경로트리: 다익스트라
모든 정점을 거치는 최소 스패닝 트리를 찾는 지금과 맞지 않는 알고리즘.
모든 정점을 거치는 최소신장트리: 크루스칼, 프림
크루스칼: edge 기반, 가장 짧은 edge부터 시작
가장 작은 edge부터 선택해 나감. 최종 전까지 한 시점에 여러 유니온 존재 가능. 선택한 edge가 사이클을 형성하는지 판별하는 union-find 알고리즘 필요.
1. root 배열에 본인으로 초기화
2. findRoot(x): root[x] != x이면 재귀적으로 반영하면서 반환하는 기능.
3. edge 배열에 간선 정렬 (동적 필요 없어서 heap 사용x)
4. 오름차순 순회, 같은 root 아니라면 유니온
import sys
input = sys.stdin.readline
V, E = map(int, input().split())
edges = []
roots = [i for i in range(V+1)]
for _ in range(E):
edges.append(list(map(int, input().split())))
edges.sort(key=lambda x: x[2])
def findRoot(x):
if x != roots[x]:
roots[x] = findRoot(roots[x]) #거치는 대표를 업데이트해가면서 반환
return roots[x]
answer = 0
for s, e, w in edges: #가중치 작은 순으로 정렬
sroot = findRoot(s)
eroot = findRoot(e)
if sroot != eroot: # 같으면 이미 유니온이라 넘어가고, 다르면 병합 시작
if sroot < eroot:
roots[eroot] = sroot #유니온 병합. 가장 작은 것을 대표로
else:
roots[sroot] = eroot
answer += w
print(answer)예를 들어 123, 456 이 한 무린데, 2랑 6을 연결할거다
sroot = 1
eroot = 4
sroot: 1 < eroot: 4이니까
roots[eroot: 4] = sroot: 1로 업데이트
findRoot(2)를 호출할 때 값들 업데이트하면서 반영
2 != roots[2]: 4
roots[2] = 1
4 != roots[4]: 1
roots[4] = 1
1 == roots[1]
프림: node 기반, heap에 아무 node부터 시작
모든 정점을 거쳐야하므로 일단 아무 정점을 선택 후, 그것에 연결된 간선 중 가장 작은 간선 선택해 나감. 한 시점에 무조건 하나의 유니온. 유니온을 확장해나가며 visited 정점을 기록하여 사이클을 방지함.
1. visited 배열 False로 초기화
2. edges[node] 기준으로 연결된 nodes 담을 것이므로 이중 배열 초기화
3. 동적 위해 heap 사용. 아무 정점 하나로 초기화 (0, 아무node)
4. 작은 간선부터 heap에 추가
5. 최소 스패닝 트리를 찾아야하므로 깊이가 V일 때 break
여기서 깊이 상관 없이 돌리고, 최단 경로 알고리즘 추가하면 다익스트라
import sys
input = sys.stdin.readline
import heapq
V, E = map(int, input().split())
edges = [[] for _ in range(V+1)]
visited = [False] * (V+1)
heap = [(0, 1)]
for _ in range(E):
s, e, w = map(int, input().split())
edges[s].append((w, e))
edges[e].append((w, s))
ans = 0
cnt = 0
while heap:
if cnt == V:
break
w, node = heapq.heappop(heap)
if visited[node]:
continue
visited[node] = True
ans += w
cnt += 1
for edge in edges[node]:
heapq.heappush(heap, edge)
print(ans)크루스탈 & 프림:
https://hillier.tistory.com/54
