[백준 1197번/JAVA] 최소 스패닝 트리

문제

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

1197번: 최소 스패닝 트리

 

최소 스패닝 트리란?

스패닝 트리 = 신장 트리 = Spanning Tree

• 그래프에서 일부 간선을 선택해 만든 트리
• 최소 연결로 이루어짐 즉, 모든 노드가 가장 적은 간선 수로 이어져있는 경우에 해당
• 정점이 n개일 때 간선이 n-1개이면 스패닝 트리
• BFS, DFS로 신장 트리 찾기 가능 (탐색 도중 사용한 간선을 모으면 됨)

최소 스패닝 트리 = 최소 비용 신장 트리 = Minimum Spanning Tree = MST

• 스패닝 트리 중 사용된 간선들의 가중치 합이 최소인 트리
• 각 간선의 가중치가 동일하지 않을 경우, 단순히 적은 간선을 쓴다고 최소비용이 되는 건 아님
• 사이클이 없어야 함

최소 스패닝 트리 구현 방법 - Kruskal

Kruskal : 탐욕적 방법(greedy method) 이용
참고

1. 간선들을 가중치의 오름차순으로 정렬
   • 간선의 양 끝 정점과 간선의 가중치를 멤버로 가지는 node클래스를 선언한다.
   • node클래스의 객체를 ArrayList에 넣은 후 가중치 기준으로 Collections.sort()처리한다.
   • node클래스 안에 Comparable의 compareTo()을 오버라이딩하면 무엇을 기준으로 정렬처리할지 지정할 수 있다. 참고
2. 정렬된 간선 리스트에서 순서대로 간선 선택
   • 정렬된 list의 처음부터 순서대로 간선을 선택하면 가장 낮은 가중치 먼저 선택됨
   • union&find 알고리즘 사용하여 사이클을 형성하는 간선 제외
3. 해당 간선을 MST 집합에 추가
4. 2-3번을 간선 개수만큼 반복

* 순환하는지 확인하는 방법?

union&find 알고리즘을 사용한다. 참고 링크

 

간선을 선택할 때마다 간선의 양 끝 정점의 부모 노드(루트 노드)를 같게 만들어 두 정점이 같은 집합에 속하게 만듦
새로운 간선의 양 끝 정점의 부모 노드가 같다면 그래프가 순환하는 것.

 

예)
노드 1과 2를 잇는 간선이 선택됨 -> 노드 1, 2의 부모 노드를 같게 만듦
노드 2와 3을 잇는 간선이 선택됨 -> 노드 2, 3의 부모 노드를 같게 만듦

 

이때 다음으로 가중치가 작은 간선의 양 끝이 노드 1, 3이라도 사이클이 생기기 때문에 선택하면 안 된다.
노드 1, 3의 부모 노드가 같은지 아닌지 판별해서 사이클이 생기는지 알 수 있다.

코드

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

public class Main {
    static List<node> list = new ArrayList<>();
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int sum = 0;
		
        //부모 노드 저장
        parent = new int[V+1];
        for(int i=0; i<parent.length; i++){
            parent[i] = i;
        }
		
        //리스트에 노드를 저장
        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());
            list.add(new node(a, b, c));
        }
        
        Collections.sort(list);
        
        //리스트에 저장된 노드를 차례로 꺼냄
        for(int i=0; i<list.size(); i++){
            node n = list.get(i);
            if(!isSameParent(n.a, n.b)){ //같은 집합에 속해있지 않으면 사이클 형성 안 되므로 union
                union(n.a, n.b);
                sum += n.c;
            }
        }
        bw.write(sum+" ");
        bw.close();
    }
    static void union(int a, int b){
        a = find(a);
        b = find(b);
        //if(a != b)
        //    parent[b] = a;
        if(x < y) parent[y] = x;
        else if(x > y) parent[x] = y;
        
    }
    static boolean isSameParent(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b)
            return false;
        return true;
    }
    static int find(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
}
class node implements Comparable<node>{
    int a, b, c;
    node(int a, int b, int c){
        this.a = a;
        this.b = b;
        this.c = c;
    }
    
    //가중치 기준으로 정렬
   public int compareTo(node n){
        return this.c - n.c;
    }
}

Note

• find함수에서 마지막에 find(parent[a]); 을 리턴하면 parent[a] = find(parent[a])를 리턴하는 것보다 훨씬 오래 걸린다. (2배 이상 차이) 원인이 뭘까
• 주의 : union할 때 x, y의 부모를 find()한 값으로 유니온해야 한다.