[백준 4386번] 별자리 만들기 (Python3)

도시 분할 계획과 마찬가지로 최소 스패닝 트리 문제를 풀고 나면 풀어야지 하고 묵혀놨던 문제이다.

 

최소 스패닝 트리 알고리즘을 공부하면 너무나 쉬운 문제

 

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)

여기에 잘 설명되어있다.

 

나의 생각이 맞았던건지 아주 빠른 시간내에 코드가 통과되었다.

 

 

오늘의 교훈) 최소 신장 트리 알고리즘은 매우 유용하다