백준 풀이
백준 / python / 1939. 중량제한
땡구리
2023. 2. 5. 21:43
https://www.acmicpc.net/problem/17142
문제 요약
다수의 섬이 중량제한이 있는 다리로 서로 연결되어있다.
시작 섬에서 끝 섬까지 이동할 수 있을 때, 다리를 무너뜨리지 않을 수 있는 가장 큰 중량을 구하라.
풀이 요약
1. $1 \sim 10^9$ 의 중량을 이분 탐색하면서 $\log10^9$ 회의 bfs/dfs 를 수행한다.
주의사항
- 이 문제를 처음 봤을 때, bfs/dfs만으로 풀 수 있다고 생각했다. 하지만 불가능하다.
내가 풀려고 했던 방식은 모든 경우의 수를 짚어가는 방식이었고 다음과 같이 구현했다.
이게 안되는 이유는 $O(V!)$ 의 시간 복잡도를 가지기 때문이다.
이분탐색과 bfs/dfs를 함께 사용하면 $O(\log{C} * (V + E)) = O (\log{C} * N)$ 에 풀 수 있다. - Union Find 로 더 빠르게 풀 수 있다고 한다.
공부 후 추가하도록 하겠다.
# 모든 경우의 수를 탐색하는 dfs 풀이
from sys import stdin, maxsize, setrecursionlimit
from collections import defaultdict
setrecursionlimit(10**6)
input = stdin.readline
N, M = map(int, input().split())
graph = defaultdict(dict)
visited = [False] * (N + 1)
weights = []
ans = []
for _ in range(M):
A, B, C = map(int, input().split())
if B in graph[A]:
C = max(C, graph[A][B])
graph[A][B] = C
graph[B][A] = C
S, E = map(int, input().split())
def dfs(curr, weight):
visited[curr] = True
weights.append(weight)
if curr == E:
ans.append(min(weights))
else:
for next in graph[curr]:
if not visited[next]:
dfs(next, graph[curr][next])
visited[curr] = False
weights.pop()
dfs(S, maxsize)
print(max(ans))
# 이분탐색과 dfs를 사용한 풀이
from sys import stdin
from collections import defaultdict
input = stdin.readline
N, M = map(int, input().split())
graph = defaultdict(dict)
ans = 0
for _ in range(M):
A, B, C = map(int, input().split())
if B in graph[A]:
C = max(C, graph[A][B])
graph[A][B] = C
graph[B][A] = C
S, E = map(int, input().split())
result = []
def dfs(start, weight):
weights = []
visited = [False] * (N + 1)
visited[start] = True
q = [start]
while q:
curr = q.pop()
for next in graph[curr]:
if not visited[next]:
if weight <= graph[curr][next]:
q.append(next)
visited[next] = True
weights.append(graph[curr][next])
return False
left = 1
right = 10**9
ans = 0
while left <= right:
mid = (left + right) // 2
if dfs(S, mid):
left = mid + 1
ans = mid
else:
right = mid - 1
print(ans)