백준 1922 (네트워크 연결) - java

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

1922번: 네트워크 연결

최소 스패닝 트리를 만들면 되는 문제이다. 지난번 포스팅에서 프림 알고리즘을 사용하였으므로 이번에는 크루스컬 알고리즘을 사용하여 문제를 해결하겠다.

 

크루스컬 알고리즘은 기본적으로 최소 비용 간선만을 선택해나가야 한다. 하지만 그러면서 별도의 사이클 판단을 해야 하기 때문에 UNION -Find 또한 사용한다. 

 

Union-Find

    static int find(int x)
    {
        if(root[x] == x)
            return x;

        else{
            return root[x] = find(root[x]);
        }
    }

    static void union(int x,int y)
    {
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;

        else
            root[x] = y;
    }

• Union - Find는 서로소 집합 문제를 해결하는데 정말 많이 사용한다. 기본 형태는 꼭 암기하도록 하자

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n = 0;
    static int m = 0;

    static int[] root;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());

        root = new int[n+1];
        for(int i=1;i<=n;i++)
        {
            root[i] = i;
        }

        st = new StringTokenizer(br.readLine(), " ");
        m = Integer.parseInt(st.nextToken());

        int[][] graph = new int[m+1][3];

        for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[i][0] = start;
            graph[i][1] = end;
            graph[i][2] = cost;

        }

        kruskal(graph);
        br.close();
    }
    static void kruskal(int[][] graph)
    {
        int cost = 0;
        Arrays.sort(graph , (x,y) -> (x[2] - y[2])); // 간선 정렬


        for(int i=1;i<=m;i++)
        {
            if(find(graph[i][0]) != find(graph[i][1])) // 사이클이 형성되지 않는다면
            {
                union(graph[i][0] , graph[i][1]); // union
                cost += graph[i][2]; // 비용 추가
            }
        }

        System.out.println(cost);
    }

    static int find(int x)
    {
        if(root[x] == x)
            return x;

        else{
            return root[x] = find(root[x]);
        }
    }

    static void union(int x,int y)
    {
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;

        else
            root[x] = y;
    }
}