[Graph] 행성 터널

행성 터널

난이도 : 🌕🌕
푼횟수 : 🟡⚪⚪

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었습니다. 왕국은 N개의 행성으로 이루어져 있습니다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 합니다.
행성은 3차원 좌표 위의 한 점으로 생각하면 됩니다. 두 행성 A($x_A$, $y_A$, $z_A$)와 B($x_B$, $y_B$, $z_B$)를 터널로 연결할 때 드는 비용은 min(|$x_A - x_B$|, |$y_A - y_B$|, |$z_A - z_B$|)입니다.
민혁이는 터널을 총 N - 1개 건설해서 모든 행성이 서로 연결되게 하려고 합니다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하세요.

입력 조건

• 첫째 줄에 행성의 개수 N이 주어집니다. (1 <= N <= 100,000)
• 다음 N개의 줄에는 각 행성의 x, y, z 좌표가 주어집니다.
• 모든 좌표의 값은 $-10^9$보다 크거나 같고, $10^9$보다 작거나 같은 정수입니다.
• 현 위치에 행성이 두 개 이상 있는 경우는 없습니다.

출력 조건

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

입력 예시
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

출력 예시
4

나의 풀이

문제 해설

이 문제는 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개의 간선만 고려해도 최적의 솔루션을 찾을 수 있다는 아이디어를 떠올릴 수 있으면 된다.
따라서 문제 풀이를 위해 고려한 총 간선의 개수는 3 x (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)

기출 : COCI
링크 : https://www.acmicpc.net/problem/2887

---

🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢

감사합니다.😊

Algorithm 카테고리 내 다른 글 보러가기