1922_네트워크 연결

사용 알고리즘: 크루스칼

사용 언어: java

 

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

public class Main_1922_네트워크연결_크루스칼 {
    static int n, m;
    static int[][] connection;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        input();
        //간선 가중치 기준으로 오름차순 정렬
        Arrays.sort(connection,(o1, o2) -> o1[2] - o2[2]); //뭔데 **
        initParent();

        int answer = 0;
        for (int i = 0; i < m; i++) {
            int com1 = connection[i][0];
            int com2 = connection[i][1];
            int val = connection[i][2];

            int p1 = find(com1); //부모 찾기
            int p2 = find(com2);

            if(p1 != p2) {
                answer += val;
                union(com1, com2);
            }
        }
        System.out.println(answer);
    }

    private static void union(int com1, int com2) {
        com1 = find(com1);
        com2 = find(com2);

        if(com1 < com2) {
            parent[com2] = com1;
        }
        else {
            parent[com1] = com2;
        }
    }

    private static int find(int x) {
        if(x == parent[x]) return x;
        return parent[x] = find(parent[x]); //맨 윗 조상 찾기
    }

    private static void initParent() {
        parent = new int[n+1];
        for (int i = 0; i < n+1; i++) {
            parent[i] = i;
        }
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        connection = new int[m][3];
        for (int i = 0; i < m; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < 3; j++) {
                connection[i][j] = Integer.parseInt(s[j]);
            }
        }
    }
}

 

 

크루스칼 연습을 위해 바로 풀어본 문제.

크루스칼... 이해는 된 거 같다. 얼마나 응용될지는 미지수

 

 

크루스칼 연습

https://www.acmicpc.net/workbook/view/1899