[백준] 1939번 중량제한 - Python / 알고리즘 중급 1/3 - 이분 탐색

ByungJik_Oh·2025년 7월 14일

[Baekjoon Online Judge]

목록 보기

192/244

💡 문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

💭 접근

이 문제는 이분 탐색을 활용한 매개 변수 탐색 문제로, 이분 탐색과 BFS를 사용하여 해결할 수도 있고, 다익스트라 알고리즘만을 사용해서도 해결할 수 있다.

이분 탐색을 활용하는 방법으론, 다리를 건널 최대 중량을 임의로 설정한 뒤, 입력으로 주어진 시작 섬(s)에서 도착 섬(e)까지 도달할 수 있는지를 판단하는 문제이다.

따라서 변수는 다음과 같이 설정했다.

start : 입력으로 주어질 수 있는 가장 작은 중량 → 1
end : 입력으로 주어질 수 있는 가장 큰 중량 → 1e9
mid : 실제로 다리를 건널 최대중량 → (start + end) // 2

변수를 위처럼 설정하고 mid 값을 조절하며 시작 섬에서 도착 섬까지 도달할 수 있는 최대중량을 찾는 문제이다.

따라서 최대 중량을 mid라고 했을 때 도착 섬에 도달할 수 있다면 중량을 더 늘릴 수 있는 가능성이 있으므로 mid를 증가시킨다.

반대로, 최대중량이 mid 일 때 도착 섬에 도달할 수 없다면 도착 섬에 도달하기 위해 가능한 다리가 없는 것이므로 mid를 감소시킨다.

📒 코드 (BFS)

# BFS 풀이
import sys
from collections import deque
input = sys.stdin.readline

def bfs(w):
    global visited

    q = deque()
    q.append(s)

    while q:
        bridges = graph[q.popleft()]

        for bridge in bridges:
            if bridge[0] == e and bridge[1] >= w:
                return True
            if bridge[1] >= w and visited[bridge[0]] == 0:
                visited[bridge[0]] = 1
                q.append(bridge[0])
    return False

def binary_search():
    global visited

    start = 1
    end = 1e9

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

        visited = [0 for _ in range(n + 1)]
        visited[s] = 1
        if bfs(mid):
            start = mid + 1
            ans = mid
        else:
            end = mid - 1
    return ans

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
s, e = map(int, input().split())
visited = [0 for _ in range(n + 1)]
visited[s] = 1

print(int(binary_search()))

📒 코드 (다익스트라)

# 다익스트라 풀이
import sys
import heapq
input = sys.stdin.readline

def dijkstra(start, end):
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)
        dist *= -1

        if now == end:
            print(dist)
            break

        if distance[now] > dist:
            continue

        for i in graph[now]:
            if dist == 0:
                distance[i[1]] = i[0]
                heapq.heappush(q, (-distance[i[1]], i[1]))
            elif distance[i[1]] < i[0] and distance[i[1]] < dist:
                distance[i[1]] = min(dist, i[0])
                heapq.heappush(q, (-distance[i[1]], i[1]))

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))

for i in range(1, n + 1):
    graph[i].sort(reverse=True)

distance = [0 for _ in range(n + 1)]
start, end = map(int, input().split())

dijkstra(start, end)