문제

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

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

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

www.acmicpc.net/problem/1939

  • 입력

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

  • 출력

첫째 줄에 답을 출력한다.

최종코드

그냥 섬? 다리? 하면 BFS/DFS가 아닐까 생각했지만 그렇게 쉬운 문제면 gold 4가 아니었겠지요. 스터디원 분께서 설명하시길 BFS와 이분탐색을 함께 사용해야 한다고 한다.

BFS랑 이분탐색을 같이 사용할 수 있다니,, 이런 문제는 또 처음이라 새로웠다. 한 번에 이해가지는 않았는데 일단 시키는대로 구현해보았다.

import sys
from collections import deque

def bfs():
    global mid, start, end, n
    q = deque([start])
    visit = [False] * (n+1)
    visit[start] = True

    while q:
        v = q.popleft()
        for node in g[v]:
            # 해당 노드를 방문하지 않았고, 중량제한이 mid 값보다 크거나 같으면 방문한다.
            if visit[node[0]] == False and node[1] >= mid:
                visit[node[0]] = True
                q.append(node[0])

    # mid 중량으로 end까지 도착 가능하면 True
    if visit[end]:
        return True
    # 중량제한으로 end까지 도착이 불가능하면 False
    else:
        return False

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
left, right = sys.maxsize, 0
for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())
    g[x].append([y, z])
    g[y].append([x, z])
    left = min(left, z)
    right = max(right, z)

start, end = map(int, sys.stdin.readline().split())

while left <= right:
    mid = (left + right) // 2
    # mid 중량으로 end까지 도착 가능하면 mid보다 크거나 같은 무게도 가능하다는 뜻이므로 left = mid + 1
    if bfs():
        left = mid + 1
    # 불가능하다면 중량을 낮춰야하므로 right = mid - 1
    else:
        right = mid - 1

print(right)

그러니까 이전에 풀었던 이분탐색 문제처럼 가능한 중량제한의 최대값을 구해야하므로 이분탐색을 사용하는데, 이 중량이 가능한지 테스트를 BFS로 한다고 생각하면 될 것 같다. 어려운 문제였다.

참고 사이트