[BOJ 2887, Python] Planetary Tunnels

Problem link

boj 2887

Classification

Graph theory, Sorting, Minimal spanning trees

Description

I'm surprised that it's been more than half a year since I first encountered this problem... but I thought it was worth documenting because it was solved with a solution that made sense to me, even though I've been neglecting Platinum issues lately.

To solve this problem formally, you can use a combination of the Union Find + Kruskal algorithm, which picks two coordinates out of a maximum of 100,000, lists their values from the smallest to the largest, and then includes the smallest trunk line.

However, this would result in a solution time of 10⁵ * 10⁵, which is roughly 10 billion cases, which would require a solution time of about 100 seconds, making it an infeasible solution method.

Tip: If we consider 1 second per 100 million operations, it is easy to compute!

So the key to this problem is how to reduce the number of cases from O(N²) to O(N).

To summarize, in the current problem, when building a spanning tree for an arbitrary point, we don't need to consider points other than neighboring points.

Consider a situation where we have arbitrary points A, B, and we need to connect them to a point C.

If the difference between their x-values (|X_A - X_B|) is the smallest value less than y, z → Assume that the x-value of the point C lies between the x-values of A and B.

1. if |X_A - X_C| + |X_B - X_C|, then the difference does not exist
2. Any arbitrary |X_A - X_B| that retains |X_A - X_C| or |X_B - X_C| that further connects C must be larger than the existing spanning tree → cannot exist as a counterexample.

Thus, if a trunk line connecting two arbitrary points is included in the minimal spanning tree of the current problem, it proves that the two points must be adjacent!

Solving this proof is the key, and I don't think the rest of the problem is much different from a typical union find problem.

---

Addition) I was getting timeouts when using PriorityQueue instead of heapq, and I was able to find an answer to that issue.

What's the difference between heapq and PriorityQueue in python?

The answer is that PriorityQueue is slower because it guarantees thread safety.

Solution code

# 행성 터널

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)