[BOJ][Java] 1197번 최소 스패닝 트리

문제 설명

문제 링크 : https://www.acmicpc.net/problem/1197

 

이 문제는 최소 신장 트리(Minimum Spanning Tree, MST) 알고리즘 구현 문제이다.

MST 알고리즘은 모든 노드들을 연결했을 때 가장 적은 비용의 간선 집합을 찾는 알고리즘이다.

간단한 MST에 대한 설명은 아래와 같다.

 

 

위와 같은 그래프가 있다고 가정한다.

정점 사이에는 가중치가 있는 간선이 있다.

MST 알고리즘은 해당 그래프의 모든 정점들을 잇는 가장 최소비용의 간선 집합을 찾는 알고리즘이다.

여기서 중요한 것은 그래프를 사이클이 생기면 안 된다는 것이다.

사이클이 존재하면 가중치의 합이 최소가 될 수 없기 때문이다.

또한 정점의 개수가 V라고 하면 정점을 최소 신장 트리를 구성하는 간선의 개수는 무조건 V-1개이다.

 

우선 간선을 기준으로 List를 생성해 준다. 이때는 새로운 클래스를 하나 생성해서

노드 2개와 가중치를 저장할 수 있도록 한다.

 

이때 가중치를 기준으로 오름차순 정렬해 준다. 이렇게 하는 이유는 간선의 합을 최소로 만들기 위함이다.

 

MST 알고리즘의 또 하나의 조건은 사이클이 존재하면 안 된다.

따라서 사이클의 여부를 판단해 줄 유니온 파인드 배열을 추가해줘야 한다.

 

이제 간선 리스트에 맨 앞에서부터 순회하며 정점끼리 연결해 준다.

이때 유니온 파인드 알고리즘을 이용해 현재 2개의 정점이 같은 집합에 속해있는지 확인해줘야 한다.

 

그다음도 역시나 유니온 파인드 알고리즘으로 사이클인지 아닌지 확인하면서 

아니라면 정점사이를 이어준다.

 

똑같이 반복해 준다.

 

이제 정점 2와 정점 5를 잇는 간선을 확인해 보니

2번 정점과 5번 정점은 현재 같은 집합에 속해있다. 

따라서 이 2개의 정점은 이어주지 않고 넘어간다.

 

이어준 간선의 개수가 정점의 개수인 V보다 하나 작아질 때까지

이어주다 V-1개가 되는 순간 멈추면 모든 정점을 잇는 최소 신장트리가 완성된다.

 

package boj;

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

public class BOJ1197 {
    static int[] heads;
    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());

        List<Edge> list = new ArrayList<>();  // 간선 저장
        heads = new int[V+1]; // 유니온 파인드 대표 노드 저장
        int answer = 0;
        int count = 0;

        for(int i = 1; i <= V; i++){
            heads[i] = i;
        }

        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.add(new Edge(s,e,c));
        }
        list.sort((o1,o2) -> o1.cost - o2.cost);

        for(int i = 0; i < list.size(); i++){
            if(count == V-1) break;

            Edge now = list.get(i);
            if(find(now.start) != find(now.end)){
                count++;
                answer += now.cost;
                union(now.start, now.end);
            }
        }

        System.out.println(answer);
    }
    static void union(int a, int b){
        int aHead = find(a);
        int bHead = find(b);

        if(aHead != bHead) heads[bHead] = aHead;
    }


    static int find(int num){
        if(num == heads[num]) return num;
        return heads[num] = find(heads[num]);
    }

    static class Edge{
        int start;
        int end;
        int cost;

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