백준 1197(최소 스패닝 트리) JAVA <MST, 크루스칼 알고리즘>

문제

1197번: 최소 스패닝 트리

v개의 정점과 e개의 간선정보를 입력 받아 최소 스패닝 트리를 출력하면 되는 문제이다.

M개의 간선정보가 주어지는데 예를 들어 1 2 3 으로 들어오면 1번 정점과 2번 정점이 간선 비용이 3으로 연결 되어 있다는 의미이다.

static class tuple{
        int x;
        int y;
        int cost;
        tuple(int x, int y, int cost){
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

3개의 정보를 저장해야 하기 때문에 위와 같은 클래스를 따로 만들어 주었다.

List<tuple>l = new LinkedList<>();
for(int i=0;i<e;i++){
    st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());
    int z = Integer.parseInt(st.nextToken());
    l.add(new tuple(x, y, z));
}

tuple 클래스를 List 형태로 저장해 준다.

Collections.sort(l, new Comparator<tuple>() {
       @Override
       public int compare(tuple o1, tuple o2) {
            return o1.cost -o2.cost;
       }
});

받은 정보를 정렬해 준다.

int ans = 0;
for(tuple t : l){
     int u = t.x, vv = t.y, c = t.cost;
     if(check(u, vv)){ //만약 u와 vv가 서로 연결이 되지 않으면(true이면 서로 연결 안되있음)
         Union(u, vv); //합쳐준다
         ans += c;
     }
}
System.out.println(ans);

---

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj1197_최소스패닝트리 {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        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());

        parent = new int[v+1];
        List<tuple>l = new LinkedList<>();
        for(int i=0;i<e;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            l.add(new tuple(x, y, z));
        }
        Collections.sort(l, new Comparator<tuple>() {
            @Override
            public int compare(tuple o1, tuple o2) {
                return o1.cost -o2.cost;
            }
        });

        int ans = 0;
        for(tuple t : l){
            int u = t.x, vv = t.y, c = t.cost;
            if(check(u, vv)){
                Union(u, vv);
                ans += c;
            }
        }
        System.out.println(ans);

    }
    static class tuple{
        int x;
        int y;
        int cost;
        tuple(int x, int y, int cost){
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
    static int find(int u){
        if(parent[u] == 0)return u;
        return parent[u] = find(parent[u]);
    }
    static void Union(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v)return;
        parent[u] = v;
    }
    static boolean check(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v)return false;
        return true;
    }
}