BOJ_1939_중량 제한 (Java)

[Gold III] 중량제한 - 1939

문제 링크

성능 요약

메모리: 50688 KB, 시간: 516 ms

분류

너비 우선 탐색, 이분 탐색, 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색, 최단 경로

제출 일자

2025년 1월 19일 20:27:43

문제 설명

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

출력

첫째 줄에 답을 출력한다.

문제 풀이

전에 풀어본 분리집합문제와 비슷했다. 같은 집합으로 형성되는지를 체크했고 이때 조건만족하면 끝내기 위해 정렬했다. 가장 튼튼한 다리를 고르기때문에 내림차순으로 찾은 다리가 최선이기 때문이다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main  {
    class Node implements Comparable<Node>{
        int from, to, weight;
        public Node(int from, int to, int weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o){
            return o.weight - weight;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M, p[];
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1939_중량제한/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        p = new int[N + 1];
        for (int i=1; i<=N; i++) {
            p[i] = i;
        }

        ArrayList<Node> nodes = new ArrayList<Node>();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            nodes.add(new Node(a, b, w));
        }
        Collections.sort(nodes);

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int res = 0;
        for(Node n : nodes){
            union(n.from, n.to);
            if(find(start) == find(end)){
                res = n.weight;
                break;
            }
        }
        
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
        br.close();
    }

    static int find(int x){
        if(x != p[x]) return p[x] = find(p[x]);
        return p[x];
    }

    static void union(int x, int y){
        int px = find(x);
        int py = find(y);
        if(px != py) {
            if(px > py) p[py] = p[px];
            else p[px] = py;
        }
    }
}