백준 2887번 - 행성 터널

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

2887번: 행성 터널

문제 설명

문제

때는 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보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

---

정답

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())

# 부모 테이블 초기화하기
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
parent = [i for i in range(n + 1)]

# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges = []
result = 0

# 행성들 좌표
X = []
Y = []
Z = []
for i in range(n):
    x, y, z = list(map(int, input().split()))
    X.append((x, i))
    Y.append((y, i))
    Z.append((z, i))
X.sort()
Y.sort()
Z.sort()

for i in range(n - 1):
    edges.append((X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1]))
    edges.append((Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]))
    edges.append((Z[i + 1][0] - Z[i][0], Z[i][1], Z[i + 1][1]))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
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)

 

---

풀이

 그래프에서 최소 신장 트리를 찾아서 총 비용을 구하는 문제입니다. 이 문제는 특이하게 행성의 좌표가 3차원으로 주어지고, 같은 축에서의 거리 중 최소 비용으로 터널을 연결하는 것입니다. 

 

 처음에는 3차원으로 모든 값을 따져보고 최소 비용으로 연결하는 것으로 구현했습니다.

import sys

input = sys.stdin.readline


# 두 행성간 터널 비용 구하기
def getCost(a, b):
    return min(abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2]))


# 특정 원소가 속한 집합을 찾기
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())
# 행성들 좌표
planets = []
for _ in range(n):
    planets.append(list(map(int, input().split())))
# 부모 테이블 초기화하기
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
parent = [i for i in range(n + 1)]
# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges = []
result = 0

for i in range(n):
    for j in range(i + 1, n):
        edges.append((getCost(planets[i], planets[j]), i, j))

 이렇게 구현하면 모든 행성사이에 간선이 연결되어 최대 100000*100000개의 간선을 만들어야 합니다. 총 100억개의 간선을 저장해야하는데, 간선하나에 1Byte라고 하면, 총 10GB의 메모리가 필요하여  메모리 초과가 나타나게 됩니다.

 x, y, z축을 각각 나눠서 정렬 후 인접한 노드들 끼리의 간선만 구해서 더하면 해결 할 수 있습니다.

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())

# 부모 테이블 초기화하기
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
parent = [i for i in range(n + 1)]

# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges = []
result = 0

# 행성들 좌표
X = []
Y = []
Z = []
for i in range(n):
    x, y, z = list(map(int, input().split()))
    X.append((x, i))
    Y.append((y, i))
    Z.append((z, i))
X.sort()
Y.sort()
Z.sort()

for i in range(n - 1):
    edges.append((X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1]))
    edges.append((Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]))
    edges.append((Z[i + 1][0] - Z[i][0], Z[i][1], Z[i + 1][1]))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
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)