[백준 4343] Arctic Network 번역 : 크루스칼 정답코드 (python, 파이썬)

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

4343번: Arctic Network

1. 문제

문제 국방부 (DND)는 무선 네트워크를 통해 여러 북부 전초 기지를 연결하고자합니다. 네트워크 구축에는 두 가지 다른 통신 기술이 사용됩니다. 모든 전초 기지에는 무선 송수신기가 있고 일부 전초 기지에는 추가로 위성 채널이 있습니다. 위성 채널이있는 2 개의 전초 기지는 위치에 관계없이 위성을 통해 통신 할 수 있습니다. 그렇지 않으면 두 전초 기지 사이의 거리가 송수신기의 전력에 따라 달라지는 D를 초과하지 않는 경우에만 무선으로 통신 할 수 있습니다. 전력이 높을수록 D가 높아지지만 비용이 더 많이 듭니다. 구매 및 유지 보수 고려 사항으로 인해 전초 기지의 송수신기는 동일해야합니다. 즉, D의 값은 모든 전초 기지 쌍에 대해 동일합니다. 당신의 임무는 트랜시버에 필요한 최소 D를 결정하는 것입니다. 모든 전초 기지 쌍 사이에는 적어도 하나의 통신 경로 (직접 또는 간접)가 있어야합니다.

입력 입력의 첫 번째 줄에는 테스트 케이스의 수인 N이 포함됩니다. 각 테스트 케이스의 첫 번째 줄에는 위성 채널 수인 1 <= S <= 100과 전초 기지 수인 S <P <= 500이 포함됩니다. P 라인이 이어지고 각 전초 기지의 (x, y) 좌표가 km 단위로 제공됩니다 (좌표는 0에서 10,000 사이의 정수입니다).

출력 각 경우에 대해 출력은 네트워크 연결에 필요한 최소 D를 제공하는 단일 라인으로 구성되어야합니다. 출력은 소수점 2 자리로 지정해야합니다.

 

2. 풀이

문제는 쉽게 말해 P개의 섬이 있고 이중 S는 서로 연결될 수 있으니 나머지에 대해 MST를 하면 된다.

크루스칼로 MST를 구하고, 그 중에서 무선으로 연결되는 곳들을 제외했을 때 가장 먼 거리(가장 마지막에 pop한) weight를 return하면 된다. 만약에 50% 에서 틀렸습니다가 뜬다면 제출형식을 print(res)에서 print('%.2f'%res)로 바꿔주면 된다. -,- 한참 헤맸다 정말..

 

3. 구현

50% 에서 오답. 못고치겠다 ㅠㅠ

import sys
import heapq

t = int(sys.stdin.readline())

def find(x, parent):
  if parent[x]==x:
    return x
  parent[x] = find(parent[x],parent)
  return parent[x]

def uni(x,y,parent):
  x = find(x, parent)
  y = find(y, parent)
  if x==y:
    return
  else:
    parent[y]=x
  return

while t:

  S,P = map(int, sys.stdin.readline().split())
  P_=P
  edges = []
  parent = [i for i in range(P+2)]
  satellites = [list(map(int, sys.stdin.readline().split())) for _ in range(P)]

  for i in range(len(satellites)):
    for j in range(i+1,len(satellites)):
      if i==j:
        continue
      p1 = satellites[i]
      p2 = satellites[j]
      w = round(((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)**0.5,2)
      heapq.heappush(edges, (w,i,j))
  # print(edges)
  cnt=0
  weight_lis=[]
  res=0
  while True:
    w,s,e = heapq.heappop(edges)
    if find(s, parent)!=find(e, parent):
      uni(s,e,parent)
      res=w
      cnt+=1
    if cnt==P-S:
      break
  # print(weight_lis)
  print('%.2f'%res)
  t-=1