BOJ - 1647 도시분할계획

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

1647번: 도시 분할 계획

최소 스패닝 트리를 구해주면 된다.

 

주의할 점은 하나인 마을을 두개로 나누고 싶다고 하고 있기 때문에 " N-2개" 의 간선만 연결해주면 된다.

위 N-2 가 핵심임.. 문제 이해를 못해서. 한참 고심함.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1647 {
    static int N, M;
    static Edge[] edges;
    static DJS djs;
    static class Edge implements Comparable<Edge> {
        int s, e, v;
        Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }

        @Override
        public int compareTo(Edge o) {
            return this.v - o.v;
        }
    }
    static class DJS {
        int[] mom;
        DJS(int n) {
            mom = new int[n+1];
            for (int i = 1; i <= n  ; i++) mom[i]=i;
        }
        public int find(int n) {
            if(n==mom[n]) return n;
            return mom[n] = find(mom[n]);
        }
        public boolean union(int a, int b) {
            a = find(a);
            b = find(b);
            if(a==b) return false;
            mom[b] = a;
            return true;
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/input_boj1647.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        djs = new DJS(N);
        edges = new Edge[M];
        int a, b, c;
        for (int i = 0; i < M ; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(a, b, c);
        }

        Arrays.sort(edges);

        Edge ed;
        long result = 0;
        int cnt = 0;
        for (int i = 0; i < M ; i++) {
            ed = edges[i];
            if(djs.union(ed.s, ed.e)){
                result += ed.v;
                cnt ++;
                if(cnt>= (N-2)) break;
            }
        }

        System.out.println(result);
    }
}