백준 1197번
https://www.acmicpc.net/problem/1197

문제

---

생각하기

---

• 크루스칼 알고리즘 문제이다.
  • 최소 신장 트리에서만 사용가능하다.
  • 유니온 파인드를 통해서 사이클이 생기지 않는 간선을 선택한다.

동작

크루스칼 알고리즘을 처음 학습하고 응용해봐서 학습 내용을 정리하려고 한다.

⭐크루스칼 알고리즘은 최소 스패닝 알고리즘이다.

⭐신장 트리 (Spanning Tree)에서만 사용가능하다.

⭐간선을 가중치 기준으로 정렬한다.

신장트리는 사이클이 없어야 한다.

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            adjList.offer(new Node(a, b, c));
        }

그래서 이 문제에서 연결되어 있는 간선 정보 adjList에서도 모두 사용하는 것이 아닌 사이클이 되지 않는 간선을 확인해서 해당 간선으로 신장 트리를 생성한다.

    private static int kruskal() {
        int weight = 0;

        while (!adjList.isEmpty()) {
            Node next = adjList.poll();

            if (find(next.start) != find(next.end)) {
                weight += next.weight;
                union(next.start, next.end);
            }
        }

        return weight;
    } // End of kruskal

해당 부분을 보고 생각한 것이 크루스칼 알고리즘은 사실 유니온 파인드를 통한 사이클 여부와, 가중치 정렬이 가장 핵심인 것 같다

결과

코드

---

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int V, E;
    private static int[] parents, ranks;
    private static PriorityQueue<Node> adjList;

    private static class Node implements Comparable<Node> {
        int start;
        int end;
        int weight;

        private Node(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    } // End of Node class

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(kruskal());
        return sb.toString();
    } // End of solve()

    private static int kruskal() {
        int weight = 0;

        while (!adjList.isEmpty()) {
            Node next = adjList.poll();

            if (find(next.start) != find(next.end)) {
                weight += next.weight;
                union(next.start, next.end);
            }
        }

        return weight;
    } // End of kruskal

    private static void union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if (aRoot == bRoot) return; // 이미 같은 집합에 속해 있음

        // 랭크가 낮은 트리를 랭크가 높은 트리 아래에 붙임
        if (ranks[aRoot] < ranks[bRoot]) {
            parents[aRoot] = bRoot;
        } else if (ranks[aRoot] > ranks[bRoot]) {
            parents[bRoot] = aRoot;
        } else {
            parents[bRoot] = aRoot;
            // 랭크가 같을 경우 한 쪽의 랭크를 증가.
            ranks[aRoot]++;
        }
    } // End of union()

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

        return parents[node] = find(parents[node]);
    } // End of find()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        parents = new int[V + 1];
        ranks = new int[V + 1];
        adjList = new PriorityQueue<>();

        for (int i = 0; i <= V; i++) {
            parents[i] = i;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            adjList.offer(new Node(a, b, c));
        }

    } // End of input()
} // End of Main class