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

🔔 문제

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

🎯 풀이방법

N개의 컴퓨터를 모두 연결할 때 필요한 최소 비용을 구하는 문제이다. 즉, 최소신장트리(Minimum Spanning Tree) 문제이다. 그래프에서 MST를 찾기 위해 크루스칼 알고리즘 또는 프림 알고리즘을 사용할 수 있다.

✔ 크루스칼 알고리즘
크루스칼 알고리즘은 기본적으로 Greedy한 선택을 바탕으로 알고리즘을 진행한다.'

1. 주어진 그래프의 모든 간선에 대해 간선의 연결비용을 낮은순으로 오름차순 정렬한다.
2. 정렬된 간선 순서대로 선택하면서, 만약 두 정점(a,b)이 같은 집합에 속해있는지 판별한다.
   2-1. 두 정점이 같은 집합에 속해 있다. → cycle이 있다고 판단하고 포함시키지 않는다.
   2-2. 두 정점이 다른 집합에 속해 있다. → 두 정점을 Union한다.
   
   

💡 이 문제를 통해 얻어갈 것

Miminum Spanning Tree + 크루스칼 알고리즘 문제

💻 Java Code

메모리 48964KB, 시간 592ms, 코드길이 1947B

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

public class Main {
    static class Edge implements Comparable<Edge> {
        int a,b,weight;

        public Edge(int a, int b, int weight) {
            this.a = a;
            this.b = b;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {  // 오름차순
            return this.weight - o.weight;
        }
    }

    static int N, M, total=0;
    static int[] parent;
    static Edge[] edges;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        parent = new int[N+1];
        for(int i=1; i<=N; i++) {
            parent[i] = i;
        }
        edges = new Edge[M];
        
        int a,b,c;
        for(int m=0; m<M; m++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            edges[m] = new Edge(a,b,c);
        }

        // 간선 비용 순으로 오름차순 정렬
        Arrays.sort(edges);

        // 낮은 비용부터 크루스칼 알고리즘 진행
        for(int i=0; i<M; i++) {
            if(find(edges[i].a) != find(edges[i].b)) {
                union(edges[i].a, edges[i].b);
                total += edges[i].weight;
            }
        }
        System.out.println(total);
    }

    private static void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        parent[pa] = pb;
    }

    private static int find(int a) {
        if(parent[a] == a)
            return a;
        return parent[a] = find(parent[a]);
    }
}