김낭만

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

백준(BOJ) 17490 일감호에 다리 놓기 파이썬(Python)

문제 링크

유니온 파인드(Union Find)로 풀 수 있는 문제.
각 건물과 가운데 와우도를 노드로, 길과 징검다리를 엣지로 생각하면 최소 스패닝 트리를 구하는 문제로 치환할 수 있다.
그러면 단순하게 크루스칼 알고리즘을 적용하면 된다.
다만, 이미 각 건물이 연결되어 있을 때에는 와우도로 가는 다리를 놓을 필요가 없음에 유의해야 한다.
그런데 사실 이 문제, 유니온 파인드가 아니라 그냥 그리디한 방식으로도 풀 수 있다.
어차피 연결된 건물들은 연속해서 있으므로, 건물을 순회하면서 와우도에 연결할 가장 작은 비용의 다리를 고르기만 해도 된다.
하지만 어쨌든 난 유니온 파인드로 풀었다.

#!python

from sys import stdin
input = stdin.readline

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

# 유니온
def union(a, b):
    ra, rb = root(a), root(b)
    parent[ra] = parent[rb] = min(ra, rb)

n, m, k = map(int, input().split())
# 크루스칼 알고리즘을 위해 간선 정렬
costs = sorted(list(zip(list(map(int, input().split())), [i for i in range(1, n + 1)])))
able = [True for _ in range(n + 1)]
for _ in range(m):
    i, j = map(int, input().split())
    i, j = min(i, j), max(i, j)
    if i == 1 and j == n:
        able[n] = False
        continue
    able[i] = False

parent = list(range(n + 1))

# 공사중이지 않아서 이미 연결된 건물끼리 유니온
for i in range(1, n):
    if able[i]:
        union(i, i + 1)
if able[n]:
    union(n, 1)

# 크루스칼 알고리즘
ans = 0
for cost, node in costs:
    if root(node) == 0:
        continue
    union(node, 0)
    ans += cost

# 돌이 충분하거나, 길이 하나 이하로 공사중이면(하나가 공사중이어도 모든 건물이 연결되어 있으므로) YES
# 그렇지 않으면 NO
print('YES' if ans <= k or sum(able) >= n else 'NO')

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑