자바(백준) 1939 중량제한(union-find)

오답 노트 & 새로 알게 된 점

3달 전에 해당 문제를 매개 변수 탐색과 bfs를 사용하여 문제를 해결했다.

 

이번에 다시 풀면서 알고리즘 분류를 보게 되었는데,

"분리 집합" 이 있었다.

 

저번에 풀었던 여행 가자 문제와 비슷한 느낌이 들었다.

여행 가자 라는 문제에서도 분리 집합이라는 키워드가 있었다.

 

그래서 해당 문제도 union-find 자료구조를 이용해서 문제를 해결했다.

 

다만 문제에서는 "한 번의 이동에 최대 중량" 을 구하게 된다.

따라서 가중치를 기준으로 내림차순 정렬을 한다.

 

정렬된 노드들을 앞에서부터 순차적으로 union 한다.

union을 하고 나서 start와 end가 이어진다면, 즉, find(start) == find(end)가 되면

이 때 가중치가 제일 큰 값일 때 이동할 수 있기 때문에 해당 가중치를 출력하고 끝내면 된다!

 

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M;
    static ArrayList<Node> A = new ArrayList<>();
    static int start, end, max = Integer.MIN_VALUE;
    static int [] parent;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        Collections.sort(A, (o1, o2)->{
            return o2.wei - o1.wei;
        });
 
        for (Node n : A) {
            union(n.from, n.to);
            if(find(start) == find(end)){
                System.out.println(n.wei);
                return;
            }
        }
    }
 
    static void union(int u, int v) {
        u = find(u);
        v = find(v);
 
        if(u == v) return;
 
        if(u > v){
            parent[u] = v;
        }
        else{
            parent[v] = u;
        }
    }
 
    static int find(int v) {
        if(v == parent[v]) return v;
 
        parent[v] = find(parent[v]);
        return parent[v];
    }
 
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
 
        parent = new int[N+1];
        for(int i = 1; i <= N; i++) parent[i] = i;
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = atoi(st.nextToken());
            int to = atoi(st.nextToken());
            int wei = atoi(st.nextToken());
 
            A.add(new Node(from, to, wei));
        }
 
        st = new StringTokenizer(br.readLine());
        start = atoi(st.nextToken());
        end = atoi(st.nextToken());
    }
 
    static class Node {
        int from, to, wei;
 
        public Node(int from, int to, int wei) {
            this.from = from;
            this.to = to;
            this.wei = wei;
        }
    }
}