백준 2887: 행성 터널 (Kruskal+Uion&Find [최소신장트리] / with Swift)

 

 

각 Node들의 좌표만 주어지기 때문에, 최소신장트리 알고리즘을 사용하려면, 

(간선 거리, 해당 간선으로 연결되는 노드 1, 해당 간선으로 연결되는 노드 2) 형태를 Edges 배열에 담아야한다.

 

우리는 n개의 node좌표만을 받기 때문에, 2중 for문으로 모든 node들 사이의 거리를 측정한다면, n(n-1) / 2로, O(n^2)의 시간복잡도를 가지게 된다..... 메모리 복잡도 또한 비례하게 된다.

 

하지만, 어차피 최단 거리를 구하는 것이므로, 시간복잡도가 훨씬 적은 "정렬"을 

1.x좌표 기준

2. y좌표 기준

3. z좌표 기준

으로 적용하면서, 

 

바로 인접해있는 Node들끼리의 간선만 우리가 취하면 된다.!

 

이유 ? (a -> b 거리가 3, b -> c 거리가 4일 때, 

a에서 c로 직통하는 간선은 우리에게 "쓸모가 없다"

그럴 바에, a -> b 간선과 b -> c 간선을 모두 취하면, 드는 비용은 같고, a와c만 연결되는 것이 아니라, b가 a,c 모두와 연결되기까지하기 때문이다.

 

따라서 이렇게 인접한 행성(Node)들끼리의 간선만 edges에 넣는다면, 시간복잡도는 O(N)으로 줄어든다.