『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

최소 신장 트리 (MST)

• 최소 신장 트리(minimum spanning tree)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.
  • 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
  • N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 $N-1$이다.
• 최소 신장 트리의 대표적인 알고리즘은 2개 가 있다.
  • 크루스칼 알고리즘
  • 프림 알고리즘
• 다른 그래프 알고리즘과는 달리 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다.
  • 에지를 기준으로 하는 알고리즘이기 대문이다.
• 사이클이 존재하면 안 되는 특징을 지니고 있기 때문에 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 한다.

핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기
   • 최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.
   • 에지 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.
   • 사이클 처리를 위한 유니온 파인드 리스트도 함께 초기화한다. 리스트의 인덱스를 해당 자리의 값으로 초기화하면 된다.
2. 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.
   • 오름차순 증렬은 input 데이터의 순서 조정을 위해 높은 자유도로 정렬할 수 있다.
3. 가중치가 낮은 에지부터 연결을 시도한다.
   • 가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다.
   • 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인한 후 사이클이 형성되지 않았을 때만 union 연산을 이용해 두 노드를 연결한다.
4. 전체 노드의 개수가 N이면 에지의 개수가 N-1이 될 때까지 과정 3 반복
5. 에지의 개수가 N-1이 되면 완성된 최소 신장 트리의 총 에지 비용 출력

최소 신장 트리 문제

백준 1197

문제 분석하기

• 최소 신장 트리를 구하는 가장 기본적인 문제이다.
• 가중치의 범위는 int형의 범위로, int를 사용해도 된다는 것을 말하고 있다.

구현

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

public class Main {
    
    static int[] unionFind;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        // 초기화
        int[][] array = new int[E][3];
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            array[i][0] = a;
            array[i][1] = b;
            array[i][2] = c;
        }

        unionFind = new int[V+1];
        for (int i = 1; i < unionFind.length; i++) {
            unionFind[i] = i;
        }

        // 오름차순 정렬
        Arrays.sort(array, (o1, o2) -> {
            return o1[2] - o2[2];
        });

        // 에지 만들기
        int edge = 0;
        int result = 0; // 가중치
        while (edge != V-1) {
            for (int[] in : array) {
                // 대표 노드 찾기
                int rep_a = myFind(in[0]);
                int rep_b = myFind(in[1]);

                if (rep_a != rep_b) {
                    // 대표 노드끼리 연결
                    myUnion(rep_a, rep_b);
                    result += in[2];
                    edge++;
                }
            }
        }

        System.out.println(result);
    }

    private static void myUnion(int a, int b) {
        if (a < b) {
            unionFind[b] = a;
        }
        else {
            unionFind[a] = b;
        }
    }

    private static int myFind(int num) {
        if (num == unionFind[num]) {
            return num;
        }
        return unionFind[num] = myFind(unionFind[num]);
    }
}