백준 13905 (세부) - java

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

13905번: 세부

문제 

빼빼로 데이를 맞아 혜빈이와 숭이는 세부에 있는 섬에 놀러 갔다. 섬은 바다 위에 떠다니는 집과 집들을 연결하는 오크나무로 되어있는 다리로 이뤄져 있다. 숭이는 혜빈이에게 깜짝 이벤트를 해주기 위해 섬 관리자에게 혜빈이를 이벤트장소에 머물게 해달라고 하였다. 이벤트 당일 날 숭이는 금으로 된 빼빼로들을 들고 이벤트 장소로 이동하려 했다. 하지만 아뿔싸! 각 다리마다 다리 위를 지날 수 있는 무게 제한이 존재했다. 비싼 금빼빼로를 가면서 버리기 아깝던 숭이는 자신이 머물던 집에서 자신이 혜빈이에게 갈 수 있는 최대한의 금빼빼로만을 들고 가려고 한다. 따라서 숭이는 인공위성조차 해킹할 수 있는 당신에게 혜빈이에게 들고 갈 수 있는 최대한의 금빼빼로 개수를 알려달라고 부탁했다. 당신은 인공위성을 해킹하여 집들의 번호와 다리의 무게제한을 알아내었다. 이 정보를 가지고 빨리 숭이를 도와주자.

(금빼빼로 하나의 무게는 1이고, 숭이의 몸무게는 고려하지 않는다.)

 

유형 : MST

 

접근 방식

• 보통 위의 문제를 보고 최대 유량을 생각할 수 있다. 하지만 MST를 이용해서 충분히 해결할 수 있는 문제이다.
• 우선 위의 문제에서 중요한 점은 MST를 만드는 것이 목적이 아니란 것이다 !
  • MST를 만드는 과정이 문제를 푸는 핵심인 것이다.
• 우선 가장 많은 양의 빼빼로를 가져가기 위해서는 무게 단위가 큰 다리를 선택해야 한다.
  • MST의 기존 방식과 반대인 무게 단위가 큰 간선부터 선택하도록 한다.
• 선택되는 간선의 무게는 진행될수록 작아질 것이다. -> 해당 값을 계속 초기화 하도록 한다.
• 언제까지 반복해야 할까?
  • 가장 중요한 접근이다. 결국 출발지와 목적지가 이어진 순간 : find(s) == find(e)
  • 결국 출발지와 목적지가 이어졌을 때 선택된 간선이 정답이다. -> 여태까지 사용한 간선들 중에 무게가 가장 작을 것이기 때문 !

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    static int s = 0;
    static int e = 0;

    static int[] root;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

        st = new StringTokenizer(br.readLine(), " ");
        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> y.c - x.c
        );

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            pq.add(new Node(v1,v2,c));
        }

        int min = 1000001;

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(find(cur.v1) != find(cur.v2))
            {
                union(cur.v1,cur.v2);
                min = Math.min(min,cur.c);
            }

            if(find(s) == find(e)){
                System.out.println(min);
                return;
            }
        }

        System.out.println(0);
        br.close();
    }

    static int find(int x){
        if(root[x] == x)
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;
        else
            root[x] = y;
    }
}
class Node{
    int v1;
    int v2;
    int c;

    Node(int v1,int v2,int c){
        this.v1 = v1;
        this.v2 = v2;
        this.c = c;
    }
}