[백준 1774번] 우주신과의 교감 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappush,heappop
from math import sqrt

N,M = map(int,input().split())

co = []
for i in range(N):
  co.append([*map(int,input().split())])

graph = [[0]*N for i in range(N)]

for i in range(N-1):
  x1,y1 = co[i]
  for j in range(i+1,N):
    x2,y2 = co[j]
    d = sqrt((x1-x2)**2+(y1-y2)**2)
    graph[i][j] = graph[j][i] = d

for i in range(M):
  x,y = map(lambda x:x-1,map(int,input().split()))
  graph[x][y] = graph[y][x] = 0

check = [0]*N
check[0] = 1
hq = []
result = 0
for i in range(N):
  heappush(hq,(graph[0][i],i))
for _ in range(N-1):
  while hq:
    d,x = heappop(hq)
    if check[x]:
      continue
    check[x] = 1
    result += d
    for i in range(N):
      if check[i]:
        continue
      heappush(hq,(graph[x][i],i))
    break

print("{:.2f}".format(result))

 

매우 전형적인 MST 문제이다. 프림 알고리즘으로 해결하였다.

 

문제를 푸는건 아주 쉬웠는데, 문제가 하나 있었다. 바로 "소수점 둘째 자리까지 출력" 이었다.

처음에는 그냥 평소 하던대로 round 함수로 반올림을 해줬는데 틀렸습니다 가 떴다.

정수를 round함수로 출력하면 4가 4.0으로 출력되는것이 문제였다.

따라서 이를 4.00으로 출력하여려면 새로운 함수인 format 함수에 대해서 알아봐야했다.

 

조금 짜증나는 문제였지만 앞으로 이런식의 출력을 요구하는 문제가 또 나올 수도 있으니 유의해야겠다.

 

 

오늘의 교훈) 요구사항을 잘 확인하고 format 함수를 활용하자