[Baekjoon 2887] 행성 터널

문제

💚Ⅴ [Baekjoon 2887 - 행성 터널]

문제 풀이 방법

모든 N개의 행성을 연결하는 N-1개의 최소한의 터널을 최소비용으로 건설해야 하기 때문에 최소 스패닝 트리(MST) 문제임을 알 수 있다!

단순 최소 스패닝 트리 문제와 다른 점이 있다면 각 경로에 대한 비용을 계산해야 한다는 점이다!

1. 각 축에 대해 location을 정렬하여, 인접한 노드 사이의 최소비용의 간선을 구한다.
2. 각 간선들을 비용을 기준으로 오름차순으로 정렬한다.
3. 비용이 가장 작은 간선부터 순회하며 사이클이 발생하지 않는 경우에만 parent 배열을 합하여 최소 스패닝 트리를 구한다.

처음 이 문제를 풀이 했을 때, N개의 노드에 대한 모든 최소비용의 간선을 구했었다. 이 때, 간선 최소비용을 구하는데만 N^2의 시간복잡도가 생겨 시간초과가 났다. 더 간단한 로직은 각 축에 대해 정렬하여 인접한 노드 사이의 간선만 구하는 것이다. 그러면 간선의 최소비용을 구하는 시간복잡도를 3*N으로 줄일 수 있다!

글 읽기 - 왜 x축, y축, z축의 인접한 간선만 생각하면 되나요?

풀이 코드

Python

import sys
input = sys.stdin.readline

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())
location = [[i]+list(map(int, input().split())) for i in range(1,N+1)]
parent = [i for i in range(N+1)]

edges = []
for p in [1,2,3]: # 각 축에 대해
    sortedLoc = sorted(location, key=lambda x:x[p])
    for i in range(N-1):
        cost = abs(sortedLoc[i][p] - sortedLoc[i + 1][p])
        edges.append((cost,sortedLoc[i][0],sortedLoc[i+1][0]))

edges.sort()

result = 0
for edge in edges:
    cost, a,b = edge
    if find_parent(parent,a) != find_parent(parent, b):
        union_parent(parent,a,b)
        result+=cost

print(result)