별자리 만들기 [백준 4386] - python

import math
import heapq
import sys
input = sys.stdin.readline

def BOJ4386() :
  
  def get_dist(x1, y1, x2, y2) :
    return math.sqrt(math.pow(x1-x2, 2) + math.pow(y1-y2, 2)) 

  n = int(input())
  stars = []
  for _ in range(n) :
    stars.append(list(map(float, input().split())))

  graph = [[] for _ in range(n+1)]
  visited = [False for _ in range(n+1)]

  for i in range(len(stars)) :
    for j in range(i+1, len(stars)) :
      x1, y1 = stars[i]
      x2, y2 = stars[j]
      cost = get_dist(x1, y1, x2, y2)
      graph[i].append([cost, j])
      graph[j].append([cost, i])

  def prim() :
    result = 0
    queue = []
    queue.append([0, 1])

    while queue :
      curr_cost, curr_node = heapq.heappop(queue)

      if visited[curr_node] == False :
        visited[curr_node] = True
        result += curr_cost
        for next_cost, next_node in graph[curr_node] :
          heapq.heappush(queue, (next_cost, next_node))

    return result

  print(prim())
BOJ4386()

 

접근방법 :

1. 최소신장트리를 구하는 문제이다. 프림알고리즘을 이용하였다.

2. 프림알고리즘은 그리디한 알고리즘으로 선택된 노드들에 연결된 간선들중 가장 낮은 가치의 간선을 선택하는 문제이다. 

가장 낮은 간선을 선택하기 위해 sort가 아닌 최소 heap을 이용하였다. 

값이 push 될때마다 낮은 가치를 기준으로 정렬되어서 들어간다.

3. 별자리 좌표를 입력받고 거리만 구하고 인덱스를 이용하여 구별할 수 있도록 하였다.

 

 

 

https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기