목록MST (1)

DonHurry

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

📖 문제 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 🔎 풀이 유니온 파인드를 활용하는 최소 신장 트리 문제입니다. 백준 1197번 최소 스패닝 트리와 비슷합니다. 해당 문제는 노드 사이의 거리가 간접적으로 주어진다는 점이 다릅니다. 별들의 2차원 좌표가 주어지기 때문에, 별들 사이의 거리를 우선적으로 구하면 됩니다. 아래 코드에서는 가장 간단한 유클리디안 거리를 이용했습니다. 💻 코드 import sys input = sys.stdin.readline # root를 찾는 함수 def find_parents..
Problem Solving 2022. 11. 15. 01:43
이전 Prev 1 Next 다음