[백준 1197] 최소 스패닝 트리 (Java) - 최소신장트리 MST

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

최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 1 복사

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1 복사

3

---

풀이

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

public class Main {
    static int N,E;
    static int[] parent;
    static Edge[] edges;
    static int count = 0;
    static int sum = 0;
    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()); // 노드개수
        E = Integer.parseInt(st.nextToken()); // 에지개수

        parent = new int[N+1]; // 노드번호 1번부터 시작
        edges = new Edge[E];

        // 에지정보 입력받기
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(start, end, value);
        }

        // 에지 value기준으로 오름차순 정렬
        Arrays.sort(edges, Comparator.comparingInt(a -> a.value));

        // 대표노드배열 parent 초기화
        for(int i=1; i<N+1; i++){
            parent[i] = i;
        }

        for(int i=0; i<E; i++){
            // count가 N-1이 될때까지 반복
            if (count > N-1) break;

            Edge edge = edges[i];
            if(find(edge.start) != find(edge.end)){
                // start, end 노드의 대표노드가 다르다면(사이클X) union 연산
                union(edge.start, edge.end);
                sum += edge.value;
                count++;
            }
        }

        System.out.println(sum);
    }
    private static int find(int a){
        if(a == parent[a]) return a; // 자기자신이 대표노드라면 index return
        return parent[a] = find(parent[a]); // 아니라면 내 대표노드의 대표노드 찾아서 넣어줌
    }

    private static void union(int a, int b){
        a = find(a);
        b = find(b);

        if(a != b){ // a와 b의 대표노드가 다르다면
            parent[b] = a; // b의 대표노드에 a의 대표노드 찾아서 넣어주기
        }
    }
}
class Edge{
    int start;
    int end;
    int value;

    public Edge(int start, int end, int value){
        this.start = start;
        this.end = end;
        this.value = value;
    }
}

• 최소신장트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.
• 최소신장 트리의 주요특징
  • 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
  • N개의 노드가 있으면 최소신장트리를 구성하는 에지의 개수는 항상 N-1개다.
• 기존 그래프를 활용한 문제는 노드를 중심으로 데이터를 저장하지만, 유니온파인드나 MST와 같은 문제는 에지중심으로 데이터를 저장한다. -> 에지리스트로 그래프 표현
  • Edge라는 클래스를 선언하여 start(시작노드), end(도착노드), value(가중치)로 구성되도록 한다.
• MST를 사용하려면 유니온파인드도 같이 구현해야 한다.
• 에지정보를 입력받고, 유니온파인드 배열 parent도 '대표노드 = 자기자신'으로 초기화 해준다.

최소신장트리 구하는 방법

• Edge를 담은 배열 edges는 value기준 오름차순으로 정렬해준다.
• 가중치가 낮은 에지부터 연결 시도한다
  • 여기서 시도라는 말은 연결하고자 하는 두 노드의 대표노드가 서로 다른지 확인한 후, 다르다면 연결해주는 것이다.
  • 대표노드가 같다면, 두 노드를 연결시켜줬을 때 사이클이 형성된다.
• 두 노드를 연결할 수 있다면, union연산을 수행하고 가중치 총합sum에 value를 더해주고, count값을 증가시켜준다.
• 위 동작을 count값이 N-1이 될 때까지 반복해준다.