[백준] 1922. 네트워크 연결

문제 링크

[백준] 1922. 네트워크 연결

풀이 과정

크루스칼 알고리즘이 적용된 기본 문제입니다.

크루스칼 알고리즘에 대한 설명은 링크에 있습니다.

프림으로도 풀었습니다.

프림 알고리즘에 대한 설명은 링크에 있습니다.

코드

크루스칼

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    static int[] parent;
    static int[] rank;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] edges = new int[M][3];

        for (int i = 0; i < M; i++) {
            edges[i][0] = sc.nextInt();
            edges[i][1] = sc.nextInt();
            edges[i][2] = sc.nextInt();
        }

        Arrays.sort(edges, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[2], o2[2]);
            }
        });

        parent = new int[N + 1];
        rank = new int[N + 1];
        for (int i = 1; i <= N; i++)
            makeSet(i);

        int cnt = 0;
        int answer = 0;
        for (int i = 0; i < M; i++) {
            int a = find(edges[i][0]);
            int b = find(edges[i][1]);

            if (a == b) continue;

            union(a, b);
            cnt++;
            answer += edges[i][2];

            if (cnt == N - 1) break;
        }

        System.out.println(answer);
    }

    static void makeSet(int x) {
        parent[x] = x;
    }

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

    static void union(int a, int b) {
        int ap = find(a);
        int bp = find(b);

        if (rank[ap] > rank[bp]) {
            parent[bp] = ap;
        } else {
            parent[ap] = bp;

            if (rank[ap] == rank[bp])
                rank[ap]++;
        }
    }
}

프림

package 최소신장트리;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class BOJ_1922_네트워크연결_Prim {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

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

        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            list.add(new Edge(a, b, c));
            list.add(new Edge(b, a, c));
        }

        boolean[] used = new boolean[N + 1];
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(0, 1, 0));

        int answer = 0;
        while (N-- > 0) {
            Edge now = null;

            while (!pq.isEmpty()) {
                now = pq.poll();

                if (!used[now.v2]) {
                    used[now.v2] = true;
                    answer += now.cost;

                    break;
                }
            }

            for (int i = 0; i < list.size(); i++) {
                if (now.v2 == list.get(i).v1 && !used[list.get(i).v2]) {
                    pq.add(list.get(i));
                }
            }
        }

        System.out.println(answer);
    }

    static class Edge implements Comparable<Edge> {
        int v1;
        int v2;
        int cost;

        public Edge(int v1, int v2, int cost) {
            this.v1 = v1;
            this.v2 = v2;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }
}