[Java] 백준 1922번 : 네트워크 연결

1. 문제

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

1922번: 네트워크 연결

 

 

2. 풀이과정

MST 문제로 Kruskal이나 Prim으로 접근할 수 있다. 노드 수가 1000개, 간선 수가 최대 100,000로 N(N-1)보다 10배 적은 수이다. 따라서 여기서는 kruskal을 활용해서 풀었다.

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

public class Main {
    static int N, p[];
    static Edge[] edges;

    public static class Edge implements Comparable<Edge> {
        int n1, n2, w;

        public Edge(int n1, int n2, int w){
            this.n1 = n1;
            this.n2 = n2;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return this.w - o.w;
        }
    }

    public static int find(int n){
        if(p[n] == 0){
            return n;
        }
        return p[n] = find(p[n]);
    }

    public static boolean union(int n1, int n2){
        n1 = find(n1);
        n2 = find(n2);
        if(n1!=n2){
            p[n2] = n1;
            return true;
        }
        return false;
    }

    public static int kruskal(){
        int result = 0, cnt = 0;
        for(Edge edge : edges){
            if(union(edge.n1, edge.n2)){
                result+=edge.w;
                if(++cnt==N-1){
                    break;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        p = new int[N+1];
        edges = new Edge[M];
        StringTokenizer st = null;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            edges[i] = new Edge(
                    Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(edges);
        System.out.println(kruskal());
    }
}

 

결과

풀이시간 : 20분