도시 분할 계획과 마찬가지로 최소 스패닝 트리 문제를 풀고 나면 풀어야지 하고 묵혀놨던 문제이다.
최소 스패닝 트리 알고리즘을 공부하면 너무나 쉬운 문제
import sys
input = sys.stdin.readline
from math import sqrt
from heapq import heappush, heappop
def findparent(x):
if parent[x] == x:
return x
parent[x] = findparent(parent[x])
return parent[x]
N = int(input())
graph = [[0]*N for i in range(N)]
co = []
for i in range(N):
co.append(tuple(map(float,input().split())))
for i in range(N):
for j in range(i+1,N):
x1,y1 = co[i]
x2,y2 = co[j]
w = sqrt((x1-x2)**2 + (y1-y2)**2)
graph[i][j] = graph[j][i] = w
connected = [0]*N
hq = []
result = 0
now = 0
for _ in range(N):
for i in range(N):
if connected[i]:
continue
heappush(hq,(graph[now][i],i))
while hq:
w,next = heappop(hq)
if connected[next]:
continue
connected[next] = 1
result += w
now = next
break
print(result)
이번 문제는 프림 알고리즘을 사용해보았다.
모든 노드 사이에 1개씩 간선이 존재하기 때문에 시간복잡도 측면에서 더 유리할 것이라 판단했기 때문이다.
또 프림 알고리즘을 한번도 구현해보지 않았기 때문에 연습한다는 의미도 있었다.
모든 간선간에 거리를 그래프로 만들고, 프림 알고리즘을 이용하면 된다.
프림 알고리즘은 https://ssabi.tistory.com/60
[알고리즘] 최소 신장 트리(Minimum Spanning Tree)
최소 신장 트리(Minimum Spanning Tree) 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미합니다. n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 됩니
ssabi.tistory.com
여기에 잘 설명되어있다.
나의 생각이 맞았던건지 아주 빠른 시간내에 코드가 통과되었다.
오늘의 교훈) 최소 신장 트리 알고리즘은 매우 유용하다