[BOJ 2887, Python] 행성 터널

TraceofLight·2023년 5월 30일
0

ProblemSolving

목록 보기
16/21
post-thumbnail

문제 링크

BOJ 2887

분류

그래프 이론, 정렬, 최소 스패닝 트리

설명

이 문제를 처음 마주하고 난 뒤 벌써 반 년이 넘게 지났다는 것에 놀라움이.. 그래도 최근에 플래티넘 문제를 소홀히 한 것 치곤 그래도 납득할 수 있다는 풀이로 해결했다는 점에서 의의가 충분하지 않았나 싶어 기록해보기로 했다.

이 문제를 정공법으로 해결하기 위해서는 최대 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)
profile
24시간은 부족한 게 맞다

0개의 댓글