[greedy] 원더랜드(최소 스패닝 트리, Union & find)

들어가면서

처음으로 최소 스패닝 트리 문제를 풀어보면서 풀이 방법과 배운점을 기록한다.

전체 코드

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

class Edge implements Comparable<Edge>{
	public int v1;
    public int v2;
    public int len;
    
    public Edge(int v1, int v2, int len){
    	this.v1 = v1;
        this.v2 = v2;
        this.len = len;
    }
    
    @Override
    public int compareTo(Edge o){
    	return this.len - o.len;
    }
}

public class Main{
	static int[] unf;

	public static int Find(int v){
    	if(v == unf[v]) return v;
        else return unf[v] = Find(unf[v]);
    }
    
    public static void Union(int a, int b){
    	int fa = Find(a);
        int fb = Find(b);
        if(fa != fb) unf[fa] = fb;
    }

	public static void main(String[] args){
    	Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        int m = in.nextInt();
        
		ArrayList<Edge> arr = new ArrayList<>();        
        unf = new int[n+1];
        
        for(int i = 1; i <= n; i++) unf[i] = i;
        for(int i = 0; i < m; i++){
        	int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            
            arr.add(new Edge(a, b, c));
        }
        
        Collections.sort(arr);
        int answer = 0;
        int cnt = 0;
        
        for(Edge ob : arr){
        	int fv1 = Find(ob.v1);
            int fv2 = Find(ob.v2);
            
           	if(fv1 != fv2){
            	answer += ob.len;
                Union(ob.v1, ob.v2);
                cnt++;
                if(cnt == n-1) break;
            }
        }
       System.out.println(answer);
    }
}

문제 풀이 흐름

각 도시와 도시를 연결하는 도로 정보가 주어졌다.

도로의 길이가 최소가 되도록 해야 하므로 도로 길이를 기준으로 오름차순으로 설정해줘야 한다.

Edge 클래스에서 Comparable<> 인터페이스를 implements하고 ArrayList의 반환타입으로 초기화한 뒤
Collections.sort() 메서드로 정렬해준다.

도로의 길이를 오름차순으로 정렬했다면 도로의 정보를 Union & Find를 사용하여 집합된 상태가 되도록 설정해줘야 한다.

오름차순으로 정렬된 arr를 하나하나 가져오면서 연관된 노드들끼리 집합으로 만든다.
여기에서 집합은 트리화 시킨다고 볼 수 있다.

도시와 도시간의 거리 정보를 입력한 값이 만약 집합 상태가 아닐 때만 트리로 연결한다.

최소 스패닝 트리 문제는 트리 형태를 구하는 문제이기 때문에 cycle을 가질 수 없다.
따라서, 해당 노드가 이미 도로가 연결되어 있는 상태에서 새로운 도로를 연결할 시 Cycle을 가질 수 있게 되므로
집합 상태가 아닐 때만 로직을 수행한다.

어떠한 상황에 Union과 Find를 사용해야할까

서로소 집합을 구해야할 때,

노드가 트리 형태로 뻗어나가는 자료구조 문제를 풀어야할 때 사용할 수 있다.

배운 점

트리와 그래프의 차이

트리는 cycle을 가질 수 없고, 그래프는 cycle을 가질 수 있다.

트리는 단방향으로 뻗어나가고, 그래프 회로로 구성되어 왕복이 가능하다.

Union과 Find는 트리 자료구조를 구할 때 사용한다

Union과 Find는 서로소 집합일 때 사용되는데, 이때 서로소 집합은 트리 형태를 갖게 된다.

트리의 최대 간선 수는 n-1

n이 노드의 수일 때 트리가 가질 수 있는 최대 간선 수는 n-1이다.

왜냐하면 트리는 단방향으로 움직이고 cycle이 존재하지 않기 때문이다.