[백준 1922] 네트워크 연결 - Java코드 (크루스칼)

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

1922번: 네트워크 연결

 

문제

 

문제 이해

문제 이해는 어렵지 않다.

N개의 노드에 대한 M개의 간선정보(from , to , cost) 가 입력되는데 ,

모든 노드를 연결되는 최소비용을 구해주면 된다. 

 

방법 이해 ★

최소비용, 최단거리 그래프 (노드) 연결 문제를 MST , Minimum Spanning Tree (최소신장트리) 라고 말한다.

Greedy (탐욕법) 문제유형 중에 대표적인 유형의 문제이다.

이런 MST 유형의 문제를 푸는 정형화된 알고리즘이 존재하는데,

바로 그 유명한 "크루스칼(Kruskal) 알고리즘" 이다.

 

크루스칼 알고리즘은 그래프 상에서 가중치를 가지는 간선의 연결 비용을 최소로 가지는 답을 구할때 쓴다.

(그냥 말이 어렵다면,  그래프문제 중에서도 최소비용을 구하는 문제에서 사용하는 코드라고 이해하자) 

 

크루스칼은 결국 유니온파인드(union-find)를 이용한다. 

# 유니온파인드(union-find)란
 
쉽게 말해 Union 메소드와 find 메소드를 가지는 구현 알고리즘을 말합니다.
Union은 트리나 그래프와 같은 알고리즘에서 상호간의 연결을 기록해주는 메소드이며,
Find는 x,y 노드간 연결성이 기록되있는지를 찾는 메소드입니다.

Find 메소드를 통해 두 노드간에 연결성을 조회하여, 연결이 존재하지 않음을 확인 후
Union 메소드를 통해 연결여부를 기록해주는 형식으로 사용합니다.

최소비용으로 연결을 기록하며, 모든 노드를 연결해야하기 때문에,

해당 객체나 배열을 비용순서로 Sort(정렬)한 후,

유니온-파인드를 통해 연결성을 기록하며 최소비용으로 모든 노드의 연결을 해줄 수 있습니다.

  

풀이

이제 백준에서 Default로

Input은 왠만하면 Scanner보다 BufferedReader를

Output은 sout보다 StringBuilder나 BufferedWriter를 사용하자!

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

// 51,112 kb	584 ms
public class Main {
    static int arr[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        arr = new int[n+1]; // 노드수만큼을 가지는 arr 생성 (0은 편의상 미사용)
        // 연결정보 초기화
        for (int i = 0; i < arr.length; i++)
            arr[i] =i;
        // input 초기화
        int networks[][] = new int[m][3];
        StringTokenizer st;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine()," ");
            networks[i][0] = Integer.parseInt(st.nextToken());
            networks[i][1] = Integer.parseInt(st.nextToken());
            networks[i][2] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(networks, Comparator.comparingInt(o->o[2])); // cost 낮은순 정렬

        int res=0;
        for (int[] network : networks) {
            if(union(network[0],network[1])) { // 연결했으면
                res += network[2]; // 비용값 더함
            }
        }
        bw.write(res+"\n");
        bw.flush();
        br.close();
        bw.close();

    }
    static int find(int a){ // 연결 끝지점 탐색
        if(a == arr[a])
            return a;
        return arr[a] = find(arr[a]); // 최적화 (값최신화 안해도 무방함)
    }
    static boolean union(int from,int to){
        int a = find(from);
        int b = find(to);
        if(a != b) { // 연결이 없으면
            arr[a] = b; // 연결정보가 없는 끝쪽에 갱신시켜야 연결이 안끝어짐 (중요★)
            return true;
        }
        return false;
    }
}

 

풀이 설명

풀이의 핵심은

1. 저장한 input 데이터를 낮은 cost 순서로 정렬 

2. Union- Find에 구현

 

밑에 유니온 파인드 코드를 보면서 추가설명을 드리자면,

static int find(int a){ // 연결 끝지점 탐색
    if(a == arr[a]) // 연결여부가 없는 leaf
        return a;
    return arr[a] = find(arr[a]); // 최적화 (값최신화 안해도 무방함)
}

Find 먼저

 

1. 연결정보를 기록하는 1차원 Array 를 가진다

유니온파인드에서는 노드의 수만큼의 1차원 array를 선언하여  연결여부를 기록해주는 용도로 사용한다.

필자는 연결을 기록할 arr을 생성할 때,  input값 (0을 사용하지 않음)에 특성상 +1 길이로 선언해주었다. 

 

아무것도 연결되있지 않은 상태는 자기자신의 인덱스를 값으로 가지고 있는 상태이다.

그러므로 단순한 index 초기화를 해준다 

// 연결정보 초기화
for (int i = 0; i < arr.length; i++)
    arr[i] =i;

 

2. Find는 leaf (끝)노드를 반환한다.

이후 Find 연산을  통해 연결정보를 탐색하는데,

자기 자신값을 가지는 경우가 계속 존재할 수 밖에없으므로,

재귀호출을 해주어도 안전하다.

 

3. 값의 최신화 

return문 안에서 arr[a] 를 갱신해주는데, 안해주어도 무방하지만, 

노드가 많은 경우, 성능을 올리는데 도움이 된다.

기존에 1과 4의 연결을 탐색할때, Find를 3번을 불러서 끝값인 4에 도달했다면,

1에 연결된 2를 무시하고 4로 바로 연결시켜버려도 무방하다.

그래도 결국 1,2 연결을 찾을때, 동일하게 leaf 노드값은 4가 나오므로 연산은 줄이면서, 연결성을 잃지 않는다.

 

이번에는 Union에서의 코드설명을 드리자면,

4. 두 노드의 leaf 노드를 비교해서 연결성을 확인한다. 

static boolean union(int from,int to){
    int a = find(from);
    int b = find(to);
    if(a != b) { // 연결이 없으면
        arr[a] = b; // 연결정보가 없는 끝쪽에 갱신시켜야 연결이 안끝어짐 (중요★)
        return true;
    }
    return false;
}

사실 유니온을 호출하기전에 Find로 연결성을 확인하기도하지만,

이렇게 유니온안에서 해주는게 더 좋다.

연결여부를 검사하는 대상이 되는 두 노드에 Leaf 노드값에 연결성을 추가해주어야

기존에 연결성을 덮어씌우지 않고 보존해줄 수 있기때문에,

반드시 find 연산을 통해 가져온 leaf노드 값에 갱신을 시켜주어야 한다.