그래프 이론, 정렬, 최소 스패닝 트리
이 문제를 처음 마주하고 난 뒤 벌써 반 년이 넘게 지났다는 것에 놀라움이.. 그래도 최근에 플래티넘 문제를 소홀히 한 것 치곤 그래도 납득할 수 있다는 풀이로 해결했다는 점에서 의의가 충분하지 않았나 싶어 기록해보기로 했다.
이 문제를 정공법으로 해결하기 위해서는 최대 10만 개의 좌표 중 2개를 골라 그 값들을 최소값부터 나열한 뒤 최소 간선부터 포함시켜 나가는 유니온 파인드 + 크루스칼 알고리즘의 조합으로 해결할 수 있다.
하지만 그렇게 풀이할 경우 105 * 105 라서 가볍게 100억 개의 경우의 수를 가지게 되고 이는 결과적으로 100초 가량의 풀이 시간을 요구하기 때문에 불가능한 풀이 방법이라고 할 수 있다.
Tip: 1억 연산 횟수 당 1초 가량으로 고려하면 연산이 용이하다!
따라서 이 문제에서의 핵심은 어떻게 O(N2) 의 경우의 수를 O(N) 단위로 내리느냐라고 할 수 있겠다.
결론부터 말하자면 현재 문제에서 임의의 점에 대해서 스패닝 트리를 작성할 때 인접한 점 이외의 점은 고려하지 않아도 된다.
임의의 점 A, B가 존재하고 C라는 점에 연결해야 하는 상황을 보자.
x값의 차이(|XA - XB|)가 y, z보다 작은 최소값인 경우
→ C라는 점의 x값이 A와 B의 x값 사이에 존재함을 가정
1) |XA - XC| + |XB - XC| 인 경우 차이가 존재하지 않음
2) |XA - XB| 를 유지하고 C를 추가로 연결하는 임의의 |XA - XC| 나 |XB - XC| 가 존재한다면 반드시 기존 스패닝 트리보다 값이 커짐 → 반례 존재로 불가
따라서 임의의 두 점을 연결하는 간선이 현 문제에서 최소 스패닝 트리에 포함된다면 그 두 점은 반드시 인접하고 있어야 한다는 증명이 된다!
이 증명을 해결하는 점이 관건이며 나머지는 일반적인 유니온 파인드 문제와 크게 다르지 않다고 생각한다.
추가) heapq 대신 PriorityQueue를 사용했을 때 시간 초과가 발생했는데 해당 이슈에 대한 답변을 찾을 수 있었다.
What's the difference between heapq and PriorityQueue in python?
PriorityQueue의 경우 Thread Safety를 보장하기 때문에 더 느리다고 한다.
# 행성 터널
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def check_union(union_info: list, now_target: int) -> int:
"""
해당 노드의 현재 유니온을 조회하는 함수
"""
if union_info[now_target] == -1:
union_info[now_target] = now_target
elif union_info[now_target] != now_target:
union_info[now_target] = check_union(union_info, union_info[now_target])
return union_info[now_target]
def make_union(union_info: list, target_1: int, target_2: int) -> None:
"""
두 점이 같은 유니온인지 확인하고 아니라면 합쳐주는 함수
"""
union_1 = check_union(union_info, target_1)
union_2 = check_union(union_info, target_2)
if union_1 == union_2:
return True
else:
if union_1 > union_2:
union_info[union_1] = union_2
else:
union_info[union_2] = union_1
return False
planet_number = int(input())
coord_list = []
for i in range(planet_number):
coord_list.append([i] + list(map(int, input().split())))
cost_queue = []
for i in range(1, 4):
coord_list.sort(key=lambda x: x[i])
for j in range(planet_number - 1):
heappush(
cost_queue,
(
coord_list[j + 1][i] - coord_list[j][i],
(coord_list[j][0], coord_list[j + 1][0]),
),
)
union_info = [-1 for _ in range(planet_number)]
total_length = 0
line_number = 0
while cost_queue:
if line_number == planet_number - 1:
break
now_length, nodes = heappop(cost_queue)
node_a, node_b = nodes
if not make_union(union_info, node_a, node_b):
total_length += now_length
line_number += 1
print(total_length)