백준 2887번: 행성 터널 (Python)

접근

Kruskal MST 알고리즘을 통해 문제를 해결할 수 있다.

MST 알고리즘 설명: 2021.05.02 - [코딩/백준 (Python)] - 백준 1197번: 최소 스패닝 트리 (Python)

백준 1197번: 최소 스패닝 트리 (Python)

이전 4386번 별자리 만들기 문제와 매우 유사해보인다. 하지만 포인트는 주어진 N, 즉 행성의 숫자가 매우 크다는 것이다. 주어진 수의 행성에 대해서 (별자리 만들기에서와 같이) 행성간의 모든 간선을 고려하면 메모리가 초과된다. 따라서 그 간선들의 수를 줄여주는 것이 중요하다.

간선을 줄일 수 있는 중요 포인트는 행성간에 간선을 연결하는 cost가 거리가 아닌 x, y, z 좌표 차이 중 가장 작은 값을 가진다는 것이다. 이 특징을 가지고 다음과 같이 고려해야 하는 간선을 줄일 수 있다.

1. 주어진 모든 행성들의 좌표를 x 값을 기준으로 오름차순으로 정렬했을 때
2. i 번째 행성과 i + 2 번째 행성을 연결하는 간선은 고려할 필요가 없다. i + 1 을 거치는 두 개의 간선과 비용이 같기 때문이다.
3. 즉 x 값을 기준으로 오름차순으로 정렬했을 때 n - 1 개의 간선만 고려하면 된다.
4. 마찬가지로 y 값, z 값을 기준으로 오름차순으로 정렬했을 때 각각 n - 1 개의 간선을 고려해준다.

n 개의 행성을 각각 연결하는 모든 간선들을 고려했을 경우 n * (n - 1) / 2 개의 간선을 고려해야 하지만 위와 같이 고려할 경우 3 * (n - 1) 개의 간선만 고려하면 된다. 이를 통해 시간과 메모리를 아낄 수 있다.

코드

import sys


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


def union(x, y):
    parent[y] = x


n = int(sys.stdin.readline())
parent = [i for i in range(n + 1)]
lines = []
stars = []
for i in range(1, n + 1):
    a, b, c = map(int, sys.stdin.readline().split())
    stars.append([a, b, c, i])
for j in range(3):
    stars.sort(key=lambda x: x[j])
    for i in range(1, n):
        lines.append((abs(stars[i - 1][j] - stars[i][j]), stars[i - 1][3], stars[i][3]))
lines.sort()
cnt = 0
ans = 0
for co in lines:
    d, a, b = co
    ar = find(a)
    br = find(b)
    if ar != br:
        union(ar, br)
        ans += d
        cnt += 1
    if cnt == n - 1:
        break
print(ans)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!