[BOJ] #1939 - 중량제한

1939번: 중량제한

 

 

** 문제 유형

• 이진 탐색

 

** 풀이

1. 다리의 개수 M은 최대 100,000이며, 중량 제한 C는 최대 1,000,000,000
2. 이진 탐색을 이용하여 O(M * logC)에 문제 해결
   • 100,000 * 30 = 3,000,000
3. 한번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 이진 탐색으로 찾음
   
   • 반복적으로 중량을 설정하여, 이동이 가능한 경로를 찾음
     • 최대 중량과 최소 중량 설정
     • 중간값은 초기화할 때 최소 중량으로 설정하고 이후에는 (최대 + 최소) // 2
     • BFS로 이동이 가능한지 확인하고, 이동 가능하면 중량을 증가시킴
       
       • 최소 중량 = 중간값 + 1
     • 이동이 불가능하면, 중량을 감소시킴
       • 최대 중량 = 중간값 - 1

 

+) BFS

• 시간 복잡도: O(간선의 개수)
• 경로가 존재하는지 확인

 

from collections import deque

# 경로 탐색
def bfs(c):
    queue = deque([start_node])
    visited = [False] * (n + 1)
    visited[start_node] = True

    while queue:
        x = queue.popleft()

        for y, weight in adj[x]:
            if not visited[y] and weight >= c: # 중량 확인
                visited[y] = True
                queue.append(y)

    return visited[end_node]

---

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

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))

    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 # mid는 현재의 중량을 의미

    if bfs(mid): # (start_node -> end_node) 이동이 가능하므로, 중량을 증가시킴 for 최대 중량 찾기
        result = mid
        start = mid + 1
    else: # 이동이 불가능하므로, 중량을 감소시킴
        end = mid - 1

print(result)