[백준] 2887. 행성 터널
Link 플래티넘 5티어 문제
문제
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
| 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min( | xA-xB | , | yA-yB | , | zA-zB | )이다. |
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
예제 입력 1
1
2
3
4
5
6
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
예제 출력 1
1
4
풀이
목표는 “최소 비용”을 출력하는 것.
| 행성은 3차원 좌표로 표현되는데, 이때 각 터널끼리의 연결 비용은 min( | xA-xB | , | yA-yB | , | zA-zB | )이다. |
터널을 총 N-1개 건설하여 모든 행성이 서로 연결되게 한다는 것은 모든 행성이 한 줄로 연결한다는 말이다.
직관적으로 이 문제를 어떻게하면 풀 수 있을지 생각해보면, 행성들을 한 줄로 연결하는 모든 경우의 수를 다 찾아 비용을 계산한 다음에 그중 최소값을 출력하면 풀 수 있는 문제이다.
하지만 이 방법은 많은 계산량을 필요로 하기 때문에 다른 풀이 방법이 필요하다.
모든 경우의 수를 다 체크하는 것이 아니라고 한다면 순간순간마다 최적이라고 생각되는 것을 선택해나가는 방식의 탐욕 알고리즘을 사용할 수 있을 것이다.
모든 간선 비용을 계산하여 정렬해놓고 한줄로 행성들을 이어나간다면 최적의 해에 도달할지도 모른다.
하지만 이 문제에는 결정적인 제한사항이 존재한다.
바로 행성들이 무조건 한 줄로 이어져야한다는 것, 즉 사이클이 존재하지 않도록 해야한다.
(두 행성의 부모노드가 같다면 사이클이 있다라고 함)
자 문제해결을 위해 이제 그럼 아래의 순서로 코드를 작성해보자.
- 간선 연결비용을 오름차순으로 정렬한다.
- 간선 정보를 하나씩 확인하면서 현재 만드려는 간선이 사이클을 발생시키는지 확인한다.
- 사이클이 발생하지 않는다면 트리에 포함시킨다.
- 1~3번의 과정을 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 신기한건 함수 이름을 find_p, union_p로 바꾸면 시간초과가 난다.
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)
if a < b:
parent[b] = a
else:
parent[a] = b
n = int(input())
parent = [i for i in range(n)]
routes = []
px, py, pz = [], [], []
result = 0
for i in range(n):
x, y, z = map(int, input().split())
px.append((x, i))
py.append((y, i))
pz.append((z, i))
px.sort()
py.sort()
pz.sort()
for i in range(n-1):
routes.append((px[i+1][0] - px[i][0], px[i][1], px[i+1][1]))
routes.append((py[i+1][0] - py[i][0], py[i][1], py[i+1][1]))
routes.append((pz[i+1][0] - pz[i][0], pz[i][1], pz[i+1][1]))
routes.sort()
for edge in routes:
cost, x, y = edge
if find_parent(parent, x) != find_parent(parent, y):
union_parent(parent, x, y)
result += cost
print(result)
이처럼 사이클이 발생하는지 발생하지 않는지 확인하면서 그때그때 최적의 값을 선택해나가는 탐욕알고리즘 중 하나를 크루스칼 알고리즘 (Kruskal Algorithm)이라고 한다.
이 알고리즘이 진짜 무조건 최소의 비용을 찾는 것이 보장되는 건지에 대한 내용은 아래의 블로그 링크를 참고하면 된다.
(Link)[https://stalker5217.netlify.app/algorithm/kruskal/]
최소 스패닝 트리를 T라고 하고, 크루스칼 알고리즘으로 구현했을 때 포함되는 간선이 최소 스패닝 트리 T에는 포함되어 있지 않다고 가정한다. 만약 크루스칼 알고리즘이 선택한 간선이 정점 u와 v를 연결한다고 하면, T는 해당 간선이 아닌 다른 어떠한 경로로 u와 v를 연결하고 있다. 이 경로에 포함된 간선 중 하나는 분명히 크루스칼이 선택한 이 간선의 가중치 보다 크다. 그렇지 않으면 해당 경로를 구성하는 간선들이 크루스칼 알고리즘에 의해 이전에 모두 선택되어 이미 u와 v를 연결하는 경로가 존재한다는 모순에 빠진다.