백준 1647번 (java) 유니온파인드, 프림

백준 1647번: 도시 분할 계획 java

관찰

양방향 간선의 도로를 이루고 있는 마을을 2개로 분리시키고 싶다
최소의 비용으로 두개의 대표자가 있는 마을로 연결하면 된다
유니온 파인드 문제 프림하고 같은 원리로 MST를 만드는데 대표가 두개 있는 버전으로 작성하면 된다!

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// 양방향 간선
// n개의 집 m개의 길
// 유지비 ( 가중치 )
// 마을을 두개로 나누고 싶음
// 대표가 두개일때까지 프림을 사용한다 간만프!
public class Main {
    static class Edge implements Comparable<Edge>{
        int s;
        int v;
        int w;
        public Edge(int s,int v,int w){
            this.s = s;
            this.v = v;
            this.w = w;
        }
        @Override
        public int compareTo(Edge o) {
            return this.w - o.w;
        }
    }
    static int n,m,res;
    static int[] p,r;
    static PriorityQueue<Edge> pq;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        p = new int[n+1];
        r = new int[n+1];
        for(int i=1;i<=n;i++){
            p[i] = i;
            r[i] = 1;
        }
        pq = new PriorityQueue<>();

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            pq.add(new Edge(s,v,w));
        }
        res = 0;
        int cnt = n-2;
        while(!pq.isEmpty() && cnt>0){
            Edge cur = pq.poll();
            if(union(cur.s,cur.v)){
                res += cur.w;
                cnt--;
            }
        }
        System.out.println(res);
    }
    private static boolean union(int s, int v) {
        int S = find(s);
        int V = find(v);
        if(S == V) return false;
        if(r[S] < r[V]){
            r[V] += r[S];
            p[S] = V;
        }
        else{
            r[S] += r[V];
            p[V] = S;
        }
        return true;
    }

    private static int find(int v) {
        if(p[v] == v) return v;
        else return p[v] = find(p[v]);
    }
}

풀이

남은 길 (UNION 된 길) 합의 최솟값을 출력하기 위해 합쳐질때마다 간선을 더해준다
그리고 N개의 마을이 있다면 N-2개의 마을이 합쳐진다면 두개의 대표로 남게 된다.
최소값으로 만들어주기 위해 PriorityQueue 를 사용하여 프림 적용!

느낀점

간만에 하는 union find 문제였는데 확실히 대표라는 개념을 들고 가니깐 수월하다!