문제

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

문제 접근

  1. n개의 섬이 있으며 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있음.

  2. 각각의 다리에는 중량제한이 있으며 이 중량제한을 초과하는 양의 물품이 다리를 지나면 다리가 무너짐.

  3. 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 문제

코드

import java.io.*;
import java.util.*;

public class Main {
    static int start, end;
    static boolean[] visited;
    static ArrayList<Node>[] adjLink;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int answer = 0;

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

        // 다리마다의 중량제한의 최댓값과 최솟값을 저장
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            max = Math.max(max, cost);
            min = Math.min(min, cost);
            adjLink[x].add(new Node(y, cost));
            adjLink[y].add(new Node(x, cost));
        }
        
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        while (min <= max) {
            // 최댓값과 최솟값으로 중간값을 생성함.
            int mid = (min + max) / 2;
            // 중간값을 생성할 때마다 visited 배열을 초기화시킴.
            visited = new boolean[n + 1];

            // 시작점부터 시작하여 도착점까지 도달할 수 있냐를 체크함.
            // 문제에서 주어지는 입력값은 무조건 시작점과 도착점이 이어져 있다고 했으니
            // bfs()에서는 다음의 중량으로 통과할 수 있는지를 따짐.
            // 통과할 수 있다면 최소 중량을 mid + 1하여 mid 값을 올리고
            // 통과할 수 없다면 최대 중량을 mid - 1하여 mid 값을 내림.
            // 이때 answer는 통과할 수 있는 상황에 결정되도록 함.
            if (bfs(mid)) {
                min = mid + 1;
                answer = mid;
            } else max = mid - 1;
        }

        bw.write(answer + "");
        bw.flush();
        br.close();
        bw.close();
    }

    public static boolean bfs(int mid) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int temp = queue.poll();

            if (temp == end) return true;

            for (int i = 0; i < adjLink[temp].size(); i++) {
                // 중량제한은 중간값보다 크거나 같아야 함.
                if (adjLink[temp].get(i).cost >= mid && !visited[adjLink[temp].get(i).n]) {
                    visited[adjLink[temp].get(i).n] = true;
                    queue.offer(adjLink[temp].get(i).n);
                }
            }
        }
        return false;
    }
}

class Node {
    int n;
    int cost;

    public Node(int n, int cost) {
        this.n = n;
        this.cost = cost;
    }
}