백준 / python / 1939. 중량제한

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

 

문제 요약

다수의 섬이 중량제한이 있는 다리로 서로 연결되어있다.

시작 섬에서 끝 섬까지 이동할 수 있을 때, 다리를 무너뜨리지 않을 수 있는 가장 큰 중량을 구하라.

 

 

풀이 요약

1. $1 \sim 10^9$ 의 중량을 이분 탐색하면서 $\log10^9$ 회의 bfs/dfs 를 수행한다.

 

주의사항

1. 이 문제를 처음 봤을 때, bfs/dfs만으로 풀 수 있다고 생각했다. 하지만 불가능하다. 
   내가 풀려고 했던 방식은 모든 경우의 수를 짚어가는 방식이었고 다음과 같이 구현했다.
   이게 안되는 이유는 $O(V!)$ 의 시간 복잡도를 가지기 때문이다.
   이분탐색과 bfs/dfs를 함께 사용하면 $O(\log{C} * (V + E)) = O (\log{C} * N)$ 에 풀 수 있다.
2. 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)