[백준] 1922 네트워크 연결 - Graph Theory / Java

• 문제 링크

1922번: 네트워크 연결

 

• 풀이 과정

그래프(네트워크) 내의 모든 정점(컴퓨터)을 가장 적은 비용으로 연결하기 위해

최소 신장 트리(Minimum Spanning Tree) 를 구현해야하며 크루스칼 알고리즘으로 풀이한다.

 

각 간선의 출발 노드(src), 도착 노드(dest), 가중치(weight) 정보를 포함하는 Edge 클래스를 생성하고,

비용을 최소로 하기 위하여 compareTo 메소드를 오버라이딩하여 간선의 가중치를 오름차순 정렬 기준으로 지정한다.

 

또한 간선의 각 정점의 부모 노드를 기록하기위하여 parent 배열을 생성, 각 노드 자기 자신을 초기값으로 지정한다.

 

이후 가중치 기준으로 오름차순으로 정렬된 모든 간선을 하나씩 선택하여

간선의 두 정점이 서로 같은 최상위 부모노드에 속하는지 find 함수를 통해 확인한다.

최상위 부모 노드가 서로 다르다면 사이클이 발생하지 않으므로 union 함수를 통해 연결하고,

아닐 경우 사이클을 발생시키지 않기 위해 건너뛴다.

 

이렇게 각 간선이 최소 신장 트리에 포함될 때마다 가중치를 누적시킨 값 cost 를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        parent = new int[n + 1];
        for (int i = 1; i <= n; i++)
            parent[i] = i;

        List<Edge> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            list.add(new Edge(src, dest, weight));
        }

        Collections.sort(list);

        int cost = 0;
        for (int i = 0; i < m; i++) {
            Edge edge = list.get(i);

            if (find(edge.src) != find(edge.dest)) {
                cost += edge.weight;
                union(edge.src, edge.dest);
            }
        }

        bw.write(cost + "\n");
        bw.flush();
    }

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

        return parent[node] = find(parent[node]);
    }

    private static void union(int src, int dest) {
        src = find(src);
        dest = find(dest);

        if (src != dest)
            parent[dest] = src;
    }

    private static class Edge implements Comparable<Edge> {
        int src, dest, weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }

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

}