[백준] 1197 최소 스패닝 트리 - Graph Theory / Java

• 문제 링크

1197번: 최소 스패닝 트리

 

• 풀이 과정

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

위 문제와 입력 형식 외에 동일한 문제이다.

최소 스패닝 트리(Minimum Spanning Tree) 를 구하기 위하여 크루스칼 알고리즘을 사용한다.

 

간선의 정보(출발 노드, 도착 노드, 가중치) 를 저장하는 Edge 클래스를 생성,

가중치를 오름차순 정렬 기준으로 지정한다.

 

부모 노드 값을 저장하는 parent 배열을 생성하고

find 함수를 통해 간선의 두 노드의 부모 노드 일치 여부(싸이클 존재 여부) 를 확인한다.

 

사이클이 없을 경우 union 함수로 연결하고 최소 비용을 누적시켜 정답으로써 출력한다.

 

• 풀이 코드

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 = new StringTokenizer(br.readLine());

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

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

        List<Edge> list = new ArrayList<>();
        for (int i = 0; i < e; 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 < e; 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;
        }
    }

}