[BOJ/Python] 백준 2887 행성 터널

문제

https://www.acmicpc.net/problem/2887

풀이

풀이

• 90368 KB, 1348 ms

import sys
input = sys.stdin.readline

N = int(input().rstrip())
nodes = []
edges = []
ans = 0
cnt = 0

# make set
p = [i for i in range(N)]

# findset
def findset(x) :
    if x != p[x] :
        p[x] = findset(p[x])
    return p[x]

def distance(a, b) :
    return min([abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2])])

for i in range(N) :
    x, y, z = map(int, input().rstrip().split())
    nodes.append([x, y, z, i])

for i in range(3) :
    nodes.sort(key = lambda x:x[i])

    for j in range(N - 1) :
        edges.append((distance(nodes[j], nodes[j + 1]), nodes[j][3], nodes[j + 1][3]))

edges.sort()

for edge in edges :
    d, x, y = edge

    # x, y 가 같은 집합이 아니면
    if findset(x) != findset(y) :
        p[findset(y)] = findset(x)
        ans += d
        cnt += 1

        if cnt == N - 1 :
            break

print(ans)

풀이 설명

이 문제에서 주의해야하는 부분은 모든 간선을 저장해두지 않고, 후보가 되는 간선만 추리는 것!

모든 간선을 다 구하려고하면 메모리에서 터진다

간선을 추리는 방법은 아래와 같다.

MST 알고리즘 중 크루스칼을 이용하여 풀었는데,

크루스칼은 간선을 가중치 오름차순으로 정렬해서 가장 가중치가 적은 간선부터 선택하는 알고리즘이다 (단, 사이클이 생기면 안됨!)

이를 이용하였을 때, x, y, z 좌표 각각에 따라 행성을 정렬하고, 인접하는 행성 간의 간선만을 MST를 구하는 간선의 후보로 추릴 수 있다.

한 가지 좌표(ex. x좌표)만을 기준으로 행성을 정렬하면 일직선상에 행성을 놓을 수 있는데(= 사이클 없음), 이는 곧 x좌표만을 기준으로 할 때 구한 MST가 된다.

따라서, x, y, z 각각을 기준으로 MST를 만들 수 있는 간선들을 후보로 추리고 이를 이용해서 MST를 구할 수 있다