백준 1197 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

최소 스패닝 트리 문제를 풀어보았다. 열심히 알고리즘을 풀어보자!

우선적으로 최소 스패닝 트리의 문제를 풀기 위해서는 Union-Find알고리즘에 대해 알아야한다. 

 

Union-Find 

- 대표적인 그래프 알고리즘으로 "합집합 찾기" 라는 뜻이 담겨 있다. 

- 상호 배타집합 Disjoint-Set이라고도 불르기도 한다. 

- 선택한 노드가 서로 같은 그래프에 속하는지 판별하기 위한 알고리즘이다. 

- Union-Find는 찾기, 초기화, 합치기로 구성되어 있다. 

찾기 (Find) : 원소 a가 주어질 때, 루트 노드의 뿌리를 찾는 Function이다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Node implements Comparable<Node>{
    int data;
    int nextNode;
    int weight;
     Node(int data, int nextNode, int weight){
        this.data = data;
        this.nextNode = nextNode;
        this.weight = weight;
    }

    @Override 
   public int compareTo(Node o){
        return this.weight - o.weight; 
   }
}
public class Baekjoon1197 {
    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 = new StringTokenizer(br.readLine());
        int v = Integer.valueOf(st.nextToken());
        int e = Integer.valueOf(st.nextToken());

        ArrayList<Node> nodeList = new ArrayList<>();
        for(int i = 0; i < e; i++){
            st = new StringTokenizer(br.readLine());
            int data = Integer.parseInt(st.nextToken());
            int nextNode = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            nodeList.add(new Node(data, nextNode, weight));
        }

        Collections.sort(nodeList);
        parent = new int [v+1];
        
        for(int i=1; i<parent.length; i++){
            parent[i] = i;
        }
        int size = nodeList.size();
        int sum = 0;
        for(int i = 0; i< size; i++){
            Node node = nodeList.get(i);
            if(!isSameParent(node.data, node.nextNode)){
                sum += node.weight;
                union(node.data, node.nextNode);
            }
        }
        bw.write(sum+"\n");
        bw.flush();
        bw.close();
        br.close();
    }
    private static boolean isSameParent(int a, int b){
        a = find(a);
        b = find(b);

        if(a==b) return true;
        else return false;
    }
    private static void union(int a, int b){
        a = find(a);
        b = find(b);

       if (a != b) {
            parent[b] = a;
       }
    }

    private static int find(int a){
        if(parent[a]==a){
            return a;
        } else {
            return parent[a] = find(parent[a]);
        }
    }
}