[알고리즘] 백준1939 중량제한 - 파이썬

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

1939번: 중량제한

 

 

[풀이 코드]

'''
- 제한이 10억일때 이진탐색
- 반복적으로 중량을 선택하고 이동이 가능한 경우를 찾는다.

다른 예제
답이 5가 나와야함
3 3
1 2 9
2 3 5
1 3 2
1 3
'''
from collections import deque

n, m = map(int,input().split())

a_list = [[] for _ in range(n+1)]
start = 1000000000
end = 1

def bfs(c):
    queue = deque([start_node])
    visited = [False] * (n+1)
    visited[start_node] = True
    while queue:
        x = queue.popleft()
        for y, weight in a_list[x]: # mid값이 거리에 해당하는 weight보다 작은지 검사
            if not visited[y] and weight >= c:
                visited[y] = True
                queue.append(y)
    return visited[end_node]

for _ in range(m): # 양방향
    a, b, c = map(int, input().split())
    a_list[a].append((b, c))
    a_list[b].append((a, c))
    start = min(start, c)
    end = max(end, c)

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)

- 이분 탐색을 통해 중량을 반복적으로 선택해야 한다. 양방향 이동이 가능하므로 인접 리스트로 구현하고 동시에 최솟값(start)을 2, 최댓값(end)을 9로 초기화한다.

 

- 이분 탐색이 동작하는 while문 안에서 bfs를 통해 다음 섬으로 이동 가능한지를 탐색한다. 만약 True를 반환하면 중량을 더 올려보고 아니라면 중량을 내려보는 과정을 거친다.