[BOJ] 2887. 행성 터널 (💎, MST)

🔗

풀이

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다.
이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

최소한의 경로, 최소한의 경비를 요구하는 최소 스패닝 트리 문제이다.

각 정점들 간의 거리는 min(|xA-xB|, |yA-yB|, |zA-zB|)로 구할 수 있다. 두 정점 간의 거리들을 x, y, z좌표 각각으로 구한 후 그 중 최소값을 택하면 된다. 각 좌표에 대한 정점들의 최소 거리를 구하는 방법은 아래와 같다. 각 좌표값들을 기준으로 모든 정점들을 정렬한다. 아래는 x좌표를 기준으로 정렬한 결과값이다.

[2, [-1, -1, -5]]
[3, [10, -4, -1]]
[0, [11, -15, -15]]
[1, [14, -5, -15]]
[4, [19, -4, 19]]

앞은 몇 번째 정점인지, 뒤는 각 정점의 xyz 좌표 값이다. x좌표에 대해 정렬했으므로 x좌표 기준 오름차순으로 나타나고 있다. 여기서 모든 정점들에 대해서 다른 모든 정점까지의 거리들을 전부 구할 필요는 없다. 이 문제에서 요구하는 것은 결국 최소 비용이기 때문에, 서로 인접한 정점간의 거리만 구하면 된다. 즉 2번 정점과 3번 정점 사이의 거리만 구하면 되고, 2번 정점과 0번 정점 사이의 거리는 굳이 구할 필요가 없다는 소리. 어차피 2번 정점에서 0번 정점으로 가는 거리 12나, 3번 정점을 거쳐서(11+1)가는 거리나 똑같다.

이렇게 해서 각 좌표 별로 정렬한 후 인접한 거리들을 구한다. 모든 거리를 다 구해서 정점의 번호가 작은 값에 앞에 오도록 한 후 dist 배열에 저장한다.

크루스칼 알고리즘을 사용해 최소 스패닝 트리를 만들기 위해서는 거리를 기준으로 오름차순 정렬을 해야 한다. dist 배열에 대해 거리 순으로 오름차순 정렬한 후 유니온파인드를 사용해 각 정점이 같은 집합에 속해있는지 확인하고 속해있지 않다면 같은 집합으로 만드는 과정을 반복하며 최소 스패닝 트리를 그려나가면 된다.

import sys
input = sys.stdin.readline

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x < y:
        parent[y] = x 
    else:
        parent[x] = y 

def find_dist(lst, k):
    global dist
    for i in range(N-1):
        x, y = lst[i][0], lst[i+1][0]
        if x < y:
            dist.append((x, y, abs(lst[i][1][k]-lst[i+1][1][k])))
        else:
            dist.append((y, x, abs(lst[i][1][k]-lst[i+1][1][k])))

N = int(input())
planet = [[i, list(map(int, input().split()))] for i in range(N)]
parent = [x for x in range(N)]
dist = []

for i in range(3):
    find_dist(sorted(planet, key=lambda x: x[1][i]), i)

dist.sort(key=lambda x: x[-1])
cost = 0
for x, y, d in dist:
    if find(x) == find(y):
        continue
    union(x, y)
    cost += d

print(cost)