백준#1939 중량제한

문제

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

• 문제 난이도: 중상(hard)
• 문제 유형: 이진 탐색
• 추천 풀이 시간: 1시간

나의 풀이

남의 풀이

• 다리의 개수 M은 최대 100,000 (10만)이며, 중량 제한 C는 최대 1,000,000,000 (1억)입니다.
• 이진 탐색을 이용하여 O(M * logC)에 문제를 해결할 수 있습니다.
• 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최대값을 이진 탐색으로 찾습니다.
• BFS를 사용하여 푸는 문제임
  

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]


def bfs(c):
    queue = deque([start_node])
    # print("inside bfs", queue)
    visited = [False] * (n + 1)
    # print("visited", n, visited)
    visited[start_node] = True
    while queue:
        x = queue.popleft()
        # print("while queue", x, adj[x])
        for y, weight in adj[x]:
            if not visited[y] and weight >= c:
                visited[y] = True
                queue.append(y)

    # print(visited[end_node])
    return visited[end_node]

start = 1000000000
end = 1

for _ in range(m):
    x, y, weight = map(int, input().split())
    adj[x].append((y, weight))
    adj[y].append((x, weight))
    # print(adj)
    start = min(start, weight)
    end = max(end, weight)

start_node, end_node = map(int, input().split())

result = start
while(start <= end):
    mid = (start + end) // 2
    if bfs(mid):
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

느낀 점

Reference

• https://leonkong.cc/posts/python-deque.html