[Java][자바][백준][1197번] 최소 스패닝 트리 - 크루스칼 알고리즘

문제 설명

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

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

입력

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

최소 스패닝 트리의 가중치가 -2147483648보다 크거나 같고, 2147483647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

 

생각

크루스칼 알고리즘 기본이다! 이번 9월 A형에서 mst관련 문제가 나왔는데 나는 전혀 몰랐고, bfs를 이용하려다 사이클을 처리하지 못해 떨어졌다 ㅠㅠ

 

크루스칼의 기본은 간선을 중심으로 생각하는 것이다.

간선의 가중치가 가장 작은 것을 고르고 후에 싸이클이 생기지 않고 모든 노드를 방문할 수 있도록 고르면 된다.

 

나는 가중치가 작은 간선을 고르기 위해 우선순위 큐를 사용했다.

간선 class 만들고 가중치에 따라 정렬될 수 있게 Comparable를 설정.

 

후에는 다음과 같은 과정을 거친다.

1. 가중치가 가장 작은 간선을 하나 꺼낸다.

2, 시작 노드와 끝 노드의 최상위 노드를 찾는다. (최상위 노드가 없다면 자기 자신이 될 것이다.)

3. 만약 최상위 노드가 같다면 사이클이 생기는 것이므로 지나간다.

4. 최상위 노드가 다르다면 union을 통해 그 간선을 고르고 가중치를 result에 더해준다.

를 간선의 개수만큼 반복해주면 된다!!

 

사실 union find 함수는 간단하므로 외우는 것을 추천한다. (참고로 문제를 풀 때는 외웠으나 다시 보니 까먹어버렸다.)

주석을 통해 설명을 더 적도록 하겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int n,m;
    static int[] parent;
    static PriorityQueue<edge> pq = new PriorityQueue<edge>();
    static int result = 0;
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        parent = new int[n+1];
        
        for(int i=0; i<n+1; i++) {
            parent[i] = i;
        }
        
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            pq.add(new edge(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
        }
        
        //시작점과 종료점의 최상위 노드를 찾아서 겹치면 사이클이 생기는 것이므로 continue를 한다.
        //아니면 union을 통해 연결하고 v 를 더해준다.
        for(int i=0; i<m; i++) {
            edge tmp = pq.poll();
            
            int a = find(tmp.s);
            int b = find(tmp.e);
            
            if(a==b) continue;
            union(a,b);
            result += tmp.v;
        }
        
        System.out.println(result);
    }
    
    //크루스칼의 기본 union find!! 외워두는게 편하다.
    public static int find(int a) {
        if(a == parent[a]) return a;
        parent[a] = find(parent[a]);
        return parent[a];
    }
    
    public static void union(int a,int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        
        if(aRoot != bRoot) {
            parent[aRoot] = b;
        } else {
            return;
        }
    }
}
 
//간선 class
//우선순위 큐를 사용하기 위해서 Comparable을 통해 정렬 우선순위를 정했다. (V 기준)
class edge implements Comparable<edge>{
    int s;
    int e;
    int v;
    
    public edge(int s,int e,int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
 
    @Override
    public int compareTo(edge arg0) {
        // TODO Auto-generated method stub
        return arg0.v >= this.v ? -1:1;
    }
}