김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 17132 두더지가 정보섬에 올라온 이유 파이썬(Python)

문제 링크

분리 집합이나 서로소 집합이라고도 불리는 유니온 파인드(Union-Find, Disjoint Set) 알고리즘 문제.
트리에서 각 노드 사이에 있는 엣지들 중 최소 가중치를 구하는 문제이다.
중요한 아이디어 중 하나는, 가능한 경우의 수는 \(n^2\)이기 때문에 각 노드 간 거리를 일일히 보는 것으로는 제 시간에 풀 수 없으리라는 점이다.
노드 간의 만족도(최소 가중치)가 같은 구간이 있기 때문에, 그 구간은 일일히 더해주지 않고 그 개수를 알아내 한번에 곱할 필요가 있다.
예를 들어, 트리의 가장 작은 가중치가 1이라고 하자. 그럼 그 엣지를 포함하는 모든 경로는 1의 만족도를 가질 것이다.
트리의 두 번째로 작은 가중치가 2라고 하자. 그럼 그 엣지를 포함하는 경로 중 1의 엣지를 포함하지 않는 경로는 모두 2의 만족도를 가질 것이다.
이렇게 반복적으로 생각하면, 가장 큰 가중치 k에 대해, 만족도가 그 가중치인 경로는 그 엣지만 포함된 경우밖에 없을 것이다.
다시 말해, 가중치가 큰 엣지부터 연결시켜 나가면 문제를 쉽게 풀 수 있다.
가장 먼저 가중치가 가장 큰 엣지를 연결해서 분리 집합을 구성하면, 두 개의 노드로 이루어져 있고, 경로는 하나이므로 만족도의 합은 1 * 1 * k일 것이다.
이는 1개의 노드가 다른 1개의 노드로 만족도 k로 연결되는 것을 의미한다
그 다음으로 가중치(l이라 하자)가 큰 엣지를 연결해서 분리 집합을 구성하면, 처음의 집합과 별개일 수도, 하나일 수도 있는데, 예를 들어 하나인 경우를 생각해 보자.
처음 집합은 원래 크기가 2(노드가 2개)였고, 새로운 집합은 크기가 1이므로 만족도의 합은 2 * 1 * l일 것이다.
이는 2개의 노드가 다른 1개의 노드로 만족도 l로 연결되는 것을 의미한다.
이를 반복하면 모든 노드를 하나의 집합으로 유니온할 수 있고, 그때 나온 만족도들의 합이 답이 된다.

#!python

from sys import stdin
input = stdin.readline
INF = float('inf')

# 파인드
def root(node):
    if parent[node][0] != node:
        parent[node] = root(parent[node][0])
    return parent[node]

# 유니온
# parent[i][0]은 부모 노드 번호, [1]은 해당 분리 집합의 크기
def union(a, b):
    ra, rb = root(a), root(b)
    parent[ra[0]] = parent[rb[0]] = (min(ra[0], rb[0]), ra[1] + rb[1])

n = int(input())
edges = []

# parent[i][0]은 부모 노드 번호, [1]은 해당 분리 집합의 크기
parent = [(i, 1) for i in range(n + 1)]
for _ in range(n - 1):
    edges.append(tuple(map(int, input().split())))

# 가중치가 큰 간선부터 유니온해야 한다
edges.sort(key=lambda x: -x[2])

# 두 집합의 크기의 곱 * 가장 작은 가중치
# 그런데 가중치 내림차순 정렬이므로 지금까지의 가중치 중 무조건 현재 가중치가 가장 작다
ans = 0
for x, y, w in edges:
    rx, ry = root(x), root(y)
    ans += rx[1] * ry[1] * w
    union(x, y)

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑