[Baekjoon] 1939번 : 중량제한

1. 문제

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

• BFS, 이진탐색 문제

// 문제
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인 다리가 존재한다는 의미이다.
서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며,
모든 다리는 양방향이다.
마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는
서로 다른 두 정수가 주어진다.
공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

// 출력
첫째 줄에 답을 출력한다.

// 예제 입력 1
3 3
1 2 2
3 1 3
2 3 2
1 3

// 예제 출력 1
3

2. 핵심 아이디어

• 다리의 개수 M은 최대 100,000이며, 중량 제한 C는 최대 1,000,000,000
• 이진 탐색을 이용하여 O(M * logC)에 문제를 해결할 수 있음
• 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 이진 탐색으로 찾음

3. Python 문제풀이

from collections import deque
import sys
input = sys.stdin.readline

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]

start = 1000000000
end = 1

n, m = map(int, input().split())
adj = [[] for _ in range(n + 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
  if bfs(mid) :
    result = mid
    start = mid + 1
  else :
    end = mid - 1

print(result)

4. Java 문제풀이

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
  static boolean check(List<Weight>[] a, int limit, int start, int end, boolean [] b) {
    if(b[start])
      return false;
    b[start] = true;
    if(start == end)
      return true;
    for(Weight v : a[start]) {
      if(v.g >= limit) {
        if(check(a, limit, v.v, end, b)){
          return true;
        }
      }
    }
    return false;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    List<Weight> [] a = (List<Weight> []) new ArrayList[n+1];

    for(int i=1; i<=n; i++)
      a[i] = new ArrayList<>();

    int max = 0;
    for(int i=0; i<m; i++) {
      int v1 = sc.nextInt();
      int v2 = sc.nextInt();
      int g = sc.nextInt();
      a[v1].add(new Weight(v2, g));
      a[v2].add(new Weight(v1, g));
      max = Math.max(g, max);
    }

    int tx = sc.nextInt();
    int ty = sc.nextInt();
    int start = 1;
    int end = max;
    int ans = 0;

    while (start <= end) {
      boolean [] b = new boolean[n+1];
      int mid = (start + end) / 2;
      if (check(a, mid, tx, ty, b)) {
        start = mid + 1;
        ans = Math.max(ans, mid);
      }
      else
        end = mid - 1;
    }
    System.out.println(ans);
  }
}

class Weight{
  int v;
  int g;

  public Weight(int v, int g) {
    this.v = v;
    this.g = g;
  }
}