[백준 1939번] 중량제한 - Python

문제

백준 1939번 중량제한

bfs와 이분 탐색을 이용하는 문제
bfs 각 노드간 가중치도 같이 저장하는 법을 처음 배웠다.

풀이

import sys
from collections import deque

input = sys.stdin.readline

def bfs(weight):
    queue = deque()
    queue.append(x)
    visited = [False] * (n+1)
    visited[x] = True

    while queue:
        island = queue.popleft()

        for i, w in graph[island]:
            if not visited[i] and w >= weight:
                visited[i] = True
                queue.append(i)

    if visited[y]: return True
    else: return False


# 섬의 개수, 다리 개수
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    # a번 섬, b번 섬, 중량제한 c
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c]) # 양방향 그래프, 인접 리스트

print(graph)

# 공장 위치(시작점, 목적지)
x, y = map(int, input().split())

start = 1
end = 10000000000

result = 0
while start <= end:
    mid = (start + end) // 2

    if bfs(mid):
        result = mid
        start = mid + 1

    else:
        end = mid - 1

print(result)

너비 우선 탐색을 사용하여 주어진 중량 이상의 다리를 통해 시작점(x)에서 목적지(y)까지 갈 수 있는지 확인한다.
이분 탐색을 활용해 x부터 y까지 가는데 건너는 다리의 최대 중량을 찾는다.

c는 최대 1,000,000,000이 될 수 있는데 이렇게까지 입력값이 크거나 '중량의 최댓값 또는 최솟값'을 구해라 이런 문제는 이분 탐색을 활용하는 문제일 확률이 높다고 99클럽 멘토님이 말씀해주셨다.

기본 bfs 탐색과 이분 탐색 코드이지만 이를 떠올리기까지가 어려웠다.

✏️ 이분 탐색 O(logN)
정렬된 데이터에 대해서만 사용 가능
탐색 범위를 반으로 줄여가며 원하는 값을 찾아내는 알고리즘
주어진 범위의 중간값(mid)을 선택하고, 만족하지 않으면 범위의 상한(end)을 낮추고,
만족하면 범위의 하한(start)을 올리는 과정을 반복하며 원하는 값(target)을 찾아낸다.
target을 찾거나, 범위의 하한이 상한보다 크거나 같아지면 멈춤.

⏰ 시간복잡도 O(logN)
bfs: 최악의 경우 모든 섬과 다리를 한 번씩만 방문하므로 O(n_섬의 수 + m_다리의 수)
이진 탐색: O(logN) N은 중량의 범위를 의미 -> O(log10억)