백준 1197 최소 스패닝 트리 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/1197

2. 코드가 나오기까지 🛠️

(1) 시간복잡도 분석 ⏳

3. 코드 🌐

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

public class Main {
    static class Dest {
        int idx;
        int w;

        public Dest (int idx, int w){
            this.idx = idx;
            this.w = w;
        }    }    static class Edge {
        int start;
        int end;
        int w;

        public Edge (int start, int end, int w) {
            this.start = start;
            this.end = end;
            this.w = w;
        }    }    static int V, E;
    static ArrayList<ArrayList<Dest>> list = new ArrayList<>();
    static ArrayList<Edge> edges = new ArrayList<>();

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

        for(int i = 0; i <= V; i ++){
            list.add(new ArrayList<>());
        }
        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            list.get(start).add(new Dest(end, weight));
            list.get(end).add(new Dest(start, weight));
            edges.add(new Edge(start, end, weight));
        }        System.out.println(prim());
    }
    public static int kruskal() {
        int answer = 0;
        int [] parents = new int [V+1];
        for(int i = 1; i < V+1; i++){
            parents[i] = i;
        }        edges.sort(Comparator.comparingInt(a -> a.w));
        for(int i = 0; i < E; i++){
            Edge now = edges.get(i);
            int a = now.start;
            int b = now.end;
            if(find(parents, a) == find(parents, b)) continue;
            union(parents, a, b);
            answer += now.w;
        }        return answer;
    }
    public static int prim(){
        int answer = 0;
        boolean [] check = new boolean[V+1];
        PriorityQueue<Dest> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.w));
        pq.add(new Dest(1,0));
        while (!pq.isEmpty()){
            Dest now = pq.poll();
            if(check[now.idx]) continue; // 중복 게산 막이
            answer += now.w; // 미방문 정점이라면, 지금에서 갈 수 있는 것 중 최소 비용 정점임 -> 방문 체크
            check[now.idx] = true;
            for(int i = 0; i < list.get(now.idx).size(); i++){
                Dest next = list.get(now.idx).get(i);
                if(check[next.idx]) continue; // 중복 계산 막이
                pq.add(next);
            }        }        return answer;
    }
    public static int find(int [] parents, int idx) {
        if(parents[idx] == idx) return idx;
        int temp = find(parents, parents[idx]);
        parents[idx] = temp;
        return parents[idx];
    }
    public static void union (int [] parents, int a, int b){
        int ancestorA = find(parents, a);
        int ancestorB = find(parents, b);
        if(ancestorA == ancestorB) return;
        if(ancestorA < ancestorB){
            parents[ancestorB] = ancestorA;
        }else {
            parents[ancestorA] = ancestorB;
        }
    }
}

4. 트러블 슈팅 or 배운 점📝