[백준] 1939 - 중량제한 [Python(파이썬)]

문제

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

1939번: 중량제한

 

풀이

그래프 탐색과 이분 탐색을 함께 사용하여 해결했다. 그래프 탐색이 조금 까다로웠는데, 결정 문제를 접합하면 좀 더 간단하게 해결이 가능했다.

 

C의 범위가 굉장히 크기에 이분 탐색을 적용해야 한다. 그래프 탐색 시 인접한 노드와 연결된 다리의 중량제한이 판별하고자 하는 값(target, == mid)과 같거나 큰 경우에만 탐색할 노드에 추가하면 된다. 그래프 탐색 도중 목표 노드(end)에 도달하면 탐색을 종료한다. 

 

코드

import sys
from collections import defaultdict, deque

def search():
    left, right = 1, max_c
    result = 1
    while left <= right:
        mid = (left+right) // 2
        if bfs(mid):
            result = mid
            left = mid+1
        else:
            right = mid-1
    return result

def bfs(target):
    visited = [0 for _ in range(n+1)]
    visited[start] = 1
    queue = deque([start])
    while queue:
        u = queue.popleft()
        if u == end:
            return True
        for v, w in g[u]:
            if not visited[v] and w >= target:
                visited[v] = 1
                queue.append(v)
    return False

# init
n, m = map(int, sys.stdin.readline().split())
g = defaultdict(list)
max_c = float('-inf')
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    g[a].append([b, c])
    g[b].append([a, c])
    max_c = max(max_c, c)
start, end = map(int, sys.stdin.readline().split())
print(search())