[백준] 1647 도시 분할 계획 - Graph Theory / Java

• 문제 링크

1647번: 도시 분할 계획

 

• 풀이 과정

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int[] parent;

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

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

        PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        parent = new int[n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            pq.offer(new Edge(src, dest, weight));
        }

        for (int i = 1; i <= n; i++)
            parent[i] = i;

        int res = 0;
        int size = 0;
        while (size < n - 2) {
            Edge edge = pq.poll();

            if (find(edge.src) != find(edge.dest)) {
                union(edge.src, edge.dest);
                res += edge.weight;
                size++;
            }
        }

        bw.write(String.valueOf(res));
        bw.flush();
    }

    private static int find(int node) {
        if (node == parent[node])
            return node;

        return parent[node] = find(parent[node]);
    }

    private static void union(int src, int dest) {
        src = find(src);
        dest = find(dest);

        if (src != dest)
            parent[dest] = src;
    }

    private static class Edge {
        int src, dest, weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

}