[Baekjoon] 2887번 행성 터널
Updated:
문제
때는 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보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
예제
Example 1:
Input:
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
Output:
4
조건
시간 제한 : 1초
메모리 제한 : 128 MB
풀이과정
내 풀이1 (메모리 초과)
sort()와 heapq를 사용해보았지만 메모리 초과가 나왔다. 크루스칼 알고리즘을 적용하는데 있어서 다른 방법이 필요하다.
import heapq
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[a] = b
else:
parent[b] = a
# n = 행성의 개수
n = int(input())
# 행성 입력
graph = []
for _ in range(n):
x, y, z = map(int, input().split())
graph.append((x, y, z))
# 간선 정리
edges = []
for i in range(n):
for j in range(i+1, n):
cost = min(abs(graph[i][0]-graph[j][0]), abs(graph[i][1]-graph[j][1]), abs(graph[i][2]-graph[j][2]))
heapq.heappush(edges, (cost, i, j))
# 루트 노드 정의
parent = [0] * (n)
for i in range(n):
parent[i] = i
result = 0
# 크루스칼 알고리즘 적용
while edges:
cost, a, b = heapq.heappop(edges)
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
내 풀이 2
책 풀이의 내용을 참고해서 코드를 짜보았다.
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[a] = b
else:
parent[b] = a
# n = 행성의 개수
n = int(input())
# 행성 입력
graph = []
for i in range(n):
x, y, z = map(int, input().split())
graph.append((x, y, z, i))
# 간선 정리
edges = []
# x로 정렬
x_graph = sorted(graph, key = lambda x : x[0])
for i in range(n - 1):
edges.append((x_graph[i+1][0]-x_graph[i][0], x_graph[i][3], x_graph[i+1][3]))
# y로 정렬
y_graph = sorted(graph, key = lambda x : x[1])
for i in range(n - 1):
edges.append((y_graph[i+1][1]-y_graph[i][1], y_graph[i][3], y_graph[i+1][3]))
# z로 정렬
z_graph = sorted(graph, key = lambda x : x[2])
for i in range(n - 1):
edges.append((z_graph[i+1][2]-z_graph[i][2], z_graph[i][3], z_graph[i+1][3]))
# 루트 노드 정의
parent = [0] * n
for i in range(n):
parent[i] = i
result = 0
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)
책 풀이
이 문제는 $N - 1$개의 터널을 설치해서 모든 행성이 연결되도록 요구하므로, 최소 신장 트리를 만드는 문제로 이해할 수 있다. 일단 크루스칼 알고리즘의 시간 복잡도는 간선의 개수가 E일 때 $O(ElogE)$이다. 이 문제에서는 기본적으로 임의의 두 노드 사이에 터널을 연결 할 수 있다고 가정하므로, 간선의 개수는 $N(N-1)/2$개가 될 것이다. $N$이 최대 100,000이라는 입력 조건을 감안해보면 이는 매우 큰 수가 될 수 있으므로, 모든 두 행성 간의 거리를 확인하는 방법으로는 문제를 해결할 수 없다.
| 하지만, 터널의 비용이 $min( | X_A-X_B | , \, | Y_A-Y_B | , \, | Z_A-Z_B | )$라고 정의되어 있다. 이러한 특징을 이용하면 고려할 간선의 개수를 줄일 수 있다. 입력을 받은 뒤에 x축, y축, z축을 기준으로 각각 정렬을 수행한다. 예를 들어 문제에서 나온 것과 같이 모든 행성의 좌표가 (11, -15, -15), (14, -5, -15), (-1, -1, -5), (10, -4, -1), (19, -4, 19)라고 해보자. 이때 x축만 고려해서 정렬을 수행하면 -1,10,11,14,19가 된다. 결과적으로 각 행성의 x축에서의 거리는 차례대로 11, 1, 3, 5가 되는 것이다. |
결과적으로 x축에 대해서는 4개의 간선만 고려하면 되는 것이다. 여기서 알아두어야 할 점은, 만약에 y축과 z축은 무시하고 오직 x축만 존재한다고 했을 때, 이러한 4개의 간선만 이용해도 항상 최소 신장 트리를 만들 수 있다는 점이다. 즉, 이러한 방법을 이용하면 최소 신장 트리를 만들지 못하는 경우는 존재하지 않는다. 결과적으로 x축, y축, z축에 대하여 정렬 이후에 각각 $N-1$개의 간선만 고려해도 최적의 솔루션(Optimal Solution)을 찾을 수 있다는 아이디어를 떠올릴 수 있으면 된다.
따라서 문제 풀이를 위해 고려한 총 간선의 개수는 $3 \times (N-1)$개가 되고, 이를 이용해 크루스칼 알고리즘을 수행하면, 제한 시간 안에 해결할 수 있다.
# 특정 원소가 속한 집합을 찾기
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 = [0] * (n + 1) # 부모 테이블 초기화
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, n + 1):
parent[i] = i
x = []
y = []
z = []
# 모든 노드에 대한 좌표 값 입력받기
for i in range(1, n + 1):
data = list(map(int, input().split()))
x.append((data[0], i))
y.append((data[1], i))
z.append((data[2], 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)
Leave a comment