[BOJ] 세부(JAVA)

[13905] 세부

www.acmicpc.net/problem/13905

 

Solution

• 크루스칼 알고리즘을 사용해 최소신장트리를 만드는 방식을 사용했다.
• 이 문제에서는 가장 큰 가중치를 구해야 하므로 최대신장트리를 만들면서 edge를 추가할 때 마다 시작점 s와 e가 이어지는지 확인하고 처음으로 이어지는 순간의 가중치가 금빼빼로의 최대 무게가 된다. (PQ에서 큰 가중치를 우선으로 뽑기때문)
• union-find에서 두 노드의 조상이 같을 때 = 두 노드 간의 경로가 존재함과 같음을 고려해서 푸는 문제이다. 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int n, m, s, e, answer;
    static int[] parents;
    static PriorityQueue<Edge> pq;
 
    static class Edge implements Comparable<Edge> {
        private int from;
        private int to;
        private int d;
 
        public Edge(int from, int to, int d) {
            this.from = from;
            this.to = to;
            this.d = d;
        }
 
        @Override
        public int compareTo(Edge o) {
            return o.d - this.d;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
 
        parents = new int[n + 1];
 
        st = new StringTokenizer(br.readLine());
        s = stoi(st.nextToken());
        e = stoi(st.nextToken());
 
 
        pq = new PriorityQueue<>();
        int from, to, d;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            from = stoi(st.nextToken());
            to = stoi(st.nextToken());
            d = stoi(st.nextToken());
 
            pq.offer(new Edge(from, to, d));
        }
 
        for (int i = 0; i <= n; i++) {
            parents[i] = i;
        }
 
        answer = 0;
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (find(edge.from) != find(edge.to)) {
                union(edge.from, edge.to);
 
                if(find(s) == find(e)){
                    answer = edge.d;
                    break;
                }
            }
        }
 
        System.out.println(answer);
    }
 
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parents[b] = a;
        }
    }
 
    private static int find(int a) {
        if (parents[a] == a) {
            return a;
        }
        return parents[a] = find(parents[a]);
    }
 
    private static int stoi(String s) {
        return Integer.parseInt(s);
    }
}