[BOJ] 백준 1922 네트워크 연결 자바 (Java)

링크 : https://www.acmicpc.net/problem/1922

문제를 풀며 고민했던 점

• 가중치가 있으니 다익스트라 알고리즘을 쓰면 되지 않을까?
• 그래프 내에 사이클 판별은 유니온 파인드 알고리즘을 써야할 것 같다
• 최소 스패닝 트리 문제인데 다익스트라 알고리즘과 유니온 파인드를 함께 쓰는게 맞을까?

밟았던 단계

• 다익스트라 구현 중 사이클 판별에 대한 의문이 생김
• 유니온 파인드를 사용해야 한다는 점 발견
• 최소 스패닝 트리에 대한 생각
• 완전 탐색으로는 문제를 해결할 수 없다는 생각
• 그리디한 알고리즘을 모색함
• 크루스칼 알고리즘을 떠올림
• 크루스칼로 구현

package b1922;

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

public class Main {
    public static class Nod implements Comparable<Nod>{
        int a;
        int b;
        int d;

        Nod(int a, int b, int d) {
            this.a = a;
            this.b = b;
            this.d = d;
        }

        @Override
        public int compareTo(Nod target) {
            return this.d <= target.d ? -1 : 1;
        }
    }

    public static int find(int a, int[] par) {
        if(par[a] == a) return a;

        return par[a] = find(par[a], par);
    }

    public static void union(int a, int b, int[] par) {
        int pa = find(a, par);
        int pb = find(b, par);

        if(pa < pb) par[pb] = pa;
        else par[pa] = pb;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());

        ArrayList<Nod> list = new ArrayList<>();

        int[] par = new int[n + 1];

        for(int i = 1; i <= n; i++) {
            par[i] = i;
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());`
            int d = Integer.parseInt(st.nextToken());

            if(a == b) continue;

            list.add(new Nod(a, b, d));
        }

        Collections.sort(list);

        int res = 0;

        for(int i = 0; i < list.size(); i++) {
            if(find(list.get(i).a, par) == find(list.get(i).b, par)) continue;

            union(list.get(i).a, list.get(i).b, par);
            res += list.get(i).d;
        }

        System.out.println(res);
    }
}