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

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

 Input 

6

9

1 2 5

1 3 4

2 3 2

2 4 7

3 4 6

3 5 11

4 5 3

4 6 8

5 6 8

 

 Output 

23

▶ 가중치 합: 2 + 3 + 4 + 6 + 8 = 23

　

▶ 최소 신장 트리를 구현하는 문제로, 크루스칼Kruskal 알고리즘 구현

최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)  

최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)

※ 다른 방법으로는 프림 알고리즘(Prim's Algorithm)이 존재

[BOJ] 1197 최소 스패닝 트리

[BOJ] 백준 1197 최소 스패닝 트리

 

 

구현

가중치가 최소인 간선을 하나씩 선택하면서 신장트리를 만드는 알고리즘

① 모든 간선을 가중치에 따라 오름차순으로 정렬.

② 가중치가 가장 낮은 간선부터 선택

     → 우선순위 큐를 이용해 ① + ② 구현.

③ 선택된 간선이 사이클을 형성여부 확인

     → Find 연산을 이용해 선택된 간선의 양끝 정점이 같은 집합인지 확인

④ 사이클을 형성하지 않으면 Union 연산처리 Disjoint-Set & Union-Find 

Disjoint-Set & Union-Find

⑤ 작업 ②~④를 반복(간선이 n-1개가 선택될때까지 수행하는 것과 동일한 결과)

※ 문제에서는 가중치의 합만 구하면 되지만,

    제출코드에서는 추가되는 간선에 대한 정보를 모두 변수에 저장.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M;
    static int[] parent;
    static PriorityQueue<Edge> pq;
    static List<Edge> mstPath;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        // 정점의 개수
        N = Integer.parseInt(br.readLine()); 
        parent = new int[N+1];      
        // Union Find 테이블 초기화 
        for(int i=1; i<=N; i++) {
            parent[i] = i;
        }
 
        // 간선의 개수
        M = Integer.parseInt(br.readLine());
        // 가중치 낮은 간선을 담기 위한 우선순위 큐
        pq = new PriorityQueue<>();
        for(int i=1; i<=M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            pq.add(new Edge(from, to, cost));
        }
         
        mstPath = new ArrayList<>();
        MSTByKruskal(); // 크루스칼 알고리즘
        printAnswer(); // 정답 출력 
    }
 
    private static void MSTByKruskal() {
        for(int i=1; i<=M; i++) {
            Edge edge = pq.poll();
            int a = find(edge.from);
            int b = find(edge.to);
             
            // 사이클을 형성하는 간선 여부 확인
            if(a == b) continue;
            union(a, b);
            mstPath.add(edge);
        }
    }
 
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }
 
    private static int find(int x) {
        if (x == parent[x])
            return x;
        return parent[x] = find(parent[x]);
    }
     
    public static void printAnswer() {
        StringBuilder sb = new StringBuilder();
        int costSum = 0; // MST 간선들의 가중치 합
        for (int i=0; i < mstPath.size(); i++) {
            costSum += mstPath.get(i).cost;
        }
        sb.append(costSum);
        System.out.println(sb.toString());
    }
}
 
class Edge implements Comparable<Edge> {
    int from, to, cost;
     
    public Edge(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
 
    @Override
    public int compareTo(Edge target) {
        // 가중치가 낮은 간선이 앞쪽에 배치
        return this.cost - target.cost;
    }
}