[백준] MST* (골드4)

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

// prim
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int v,e, sum;
    static int[][] graph;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        graph = new int [v+1][v+1];
        for(int i=1;i<=e;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph[a][b] = c;
            graph[b][a] = c;
        }

        prim();
    }

    static void prim(){
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{1,0});
        int cnt = 0;
        boolean[] visit = new boolean[v+1];

        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            if(visit[cur[0]]) continue;

            visit[cur[0]] = true;
            sum += cur[1];
            cnt++;

            if(cnt == v) break;

            for(int i=1;i<=v;i++){
                if(graph[cur[0]][i] == 0 || visit[i]) continue;
                pq.offer(new int[]{i, graph[cur[0]][i]});
            }
        }

        System.out.println(sum);
    }
}

=> 메모리 초과 => arraylist로 변경

// prim
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int v,e, sum;
    static ArrayList<int[]>[] graph;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        graph = new ArrayList[v+1];
        for(int i=0;i<=v;i++){
            graph[i] = new ArrayList<>();
        }
        for(int i=0;i<e;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph[a].add(new int[]{b,c});
            graph[b].add(new int[]{a, c});
        }

        prim();
    }

    static void prim(){
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{1,0});
        int cnt = 0;
        boolean[] visit = new boolean[v+1];

        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            if(visit[cur[0]]) continue;

            visit[cur[0]] = true;
            sum += cur[1];
            cnt++;

            if(cnt == v) break;


            for(int[] edge:graph[cur[0]]){
                if(edge[0] != 0 && !visit[edge[0]])
                    pq.offer(new int[]{edge[0], edge[1]});
            }

        }

        System.out.println(sum);
    }
}

// Kruskal
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int v,e, sum;
    static Edge[] edges;
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        edges = new Edge[e];
        for(int i=0;i<e;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(a,b,c);
        }

        Kruskal();
    }
    static class Edge{
        int a,b,c;
        Edge(int a, int b, int c){
            this.a=a;
            this.b=b;
            this.c=c;
        }
    }
    static void Kruskal(){
        Arrays.sort(edges, (a,b) -> a.c-b.c);
        parent = new int[v+1];
        for(int i=1;i<=v;i++){
            parent[i] = i;
        }

        int cnt = 0;

        for(int i=0;i<e;i++){
            Edge e = edges[i];
            if(union(e.a,e.b)){
                sum += e.c;
                cnt++;
                if(cnt==v-1) break;
            }
        }
        System.out.println(sum);
    }
    static int find(int x){
        return parent[x]==x ? x : (parent[x]=find(parent[x]));
    }
    static boolean union(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return false;
        else parent[b] = a;

        return true;
    }
}