[Python] 백준 1774 우주신과의 교감 | 크루스칼 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

21924번: 도시 건설

 

 

문제 해결 포인트

- 크루스칼 알고리즘

 

- dots : 각 점(정점, 노드) 별 x, y 좌표 저장

- edges : 간선의 비용 기준으로 오름차순

- parent : 정점 별 속한 집합 정보

 

- 각 정점 정보를 순서대로 dots에 저장

- 이미 연결된 정점들을 union 함수를 이용하여 같은 집합에 속하도록 연결

 

- 가능한 모든 간선 ( 이미 연결된 간선은 포함하지 않는다 )의 정보를 edges에 저장

- edges를 간선 비용을 기준으로 오름차순 정렬 후 사이클이 발생하지 않는다면 연결

 

- 최종 결과를 "{:.2f}".format(result) 문법을 이용하여 모든 수가 소수점 2자리까지 보이도록 출력

 

 

작성 코드

import sys
import math
input = sys.stdin.readline


N, M = map(int, input().split())
dots = []
edges = []
parent = [i for i in range(N+1)]
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a, b = find(a), find(b)
    minP, maxP = min(a, b), max(a, b)
    parent[maxP] = minP


for _ in range(N):  # 정점
    x, y = map(int, input().split())
    dots.append((x, y))

for _ in range(M):  # 이미 연결된 간선
    a, b = map(int, input().split())
    union(a, b)

# 가능한 모든 간선 구하기
for i in range(N):
    for j in range(i+1, N):
        if find(i+1) != find(j+1):  # (주의)연결되어 있지 않을 때
            edges.append((math.sqrt((dots[i][0]-dots[j][0])**2 + (dots[i][1]-dots[j][1])**2), i+1, j+1))  # (비용, 점a , 점b)

edges.sort()  # 간선 비용 오름차순 정렬
result = 0
# print(edges)

for w, a, b in edges:  # 최소 간선부터 모든 노드가 연결 될 때까지 반복
    if find(a) != find(b):
        union(a, b)
        result += w

print("{:.2f}".format(result))  # (주의) 4.0이라도 4.00으로 나오도록 출력

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

---

REFERENCE

https://blockdmask.tistory.com/534