[백준(BOJ)] 13905번 세부

문제

https://www.acmicpc.net/problem/13905

13905번: 세부

바다 위에 떠다니는 집과 집들을 연결하는 다리가 있고 다리 위를 지날 수 있는 무게 제한이 있다. 집들의 번호와 다리의 무게 제한 정보를 가지고 출발 위치에서 도착 위치까지 들고 갈 수 있는 빼빼로의 최대 개수를 구하는 문제다. 

예시

Example 1:

Input: 7 9
	1 5
	1 2 2
	1 7 4
	2 3 5
	3 7 5
	4 6 1
	6 7 4
	5 6 3
	5 7 1
	3 5 2
Output: 3

힌트

출처 : 백준 13905번 문제

 

1 -(4)-> 7 -(4)-> 6 -(3)-> 3
min(4, 4, 3) = 3

풀이

from sys import stdin, setrecursionlimit

input = stdin.readline
# Python은 재귀 함수를 최대 1500번까지 호출할 수 있어 이보다 많은 호출을 하려면 sys.setrecursionlimit 로 제한을 늘릴 수 있다.
setrecursionlimit(10 ** 5)

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    parent[root_x] = root_y

n, m = map(int, input().split())
s, e = map(int, input().split())

bridge = []
for _ in range(m):
    idx, adj, cost = map(int, input().split())
    bridge.append((cost, idx, adj))
bridge.sort()

# 각 집의 부모를 자기 자신으로 초기화
parent = list(range(n + 1))
last = 0

while find(s) != find(e) and bridge:
    d, x, y = bridge.pop()
    last = d
    union(x, y)

result = last if find(s) == find(e) else 0
print(result)

 

- 크루스칼 알고리즘을 활용해 최소 신장 트리 문제를 풀어준다.

- Union-Find(Disjointed Set) 자료구조의 find 연산을 통해 부모 노드를 찾아 반환하고, Unoin 연산을 통해 두 집합을 합쳐준다.