최소신장트리

44_행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 happenundo.tistory.com

2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 최소 신장 트리를 구하면 되는 문제이다. 하지만 이전 문제들보다 어려운 점이 있다면, 노드(행성)들 사이에 연결된 간선에 대한 정보가 주어져 있지 않다. 각 노드들의 좌표들만 주어져 있고, 두 노드의 좌표를 사용해 두 노드 간의 간선 비용을 구할 수 있다. 행성의 개수 N이 최대 10만개이므로 모든 노드의 거리를 구해서 크루스칼 알고리즘을 사용하려면 O(N(N+1) / 2)의 시간이 걸리고, 이는 무조건 시간 초과가 발생한다. 밑..

문제를 읽어보면, 가로등이 켜진 도로만을 이용해서, 모든 두 집이 서로 도달 가능해야 한다는 조건을 제시한다. 이 때, 최소한의 비용으로 모든 집을 연결해야 하므로, 전형적인 최소 신장 트리 문제라는 것을 확인할 수 있다. 전형적인 크루스칼 알고리즘 문제다. 내 풀이 코드 # 어두운 길 # 특정 노드가 속한 집합을 찾는 함수 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 노드가 속한 집합을 합치는 함수 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) ..