BOJ_1197 : 최소 스패닝 트리

👉 문제링크

1197번: 최소 스패닝 트리

---

🔸 문제 분석 🔸

• 최소 신장 트리(MST, Minimum Spanning Tree)를 구현하는 문제이다.
• 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있는데, 여기서는 크루스칼을 사용했다.

🔸 문제 풀이 🔸

• 크루스칼 알고리즘의 기본 형태를 구현한다.
  • 간선을 가중치 기준으로 오름차순 정렬하기 위해 우선순위 큐를 사용했다.
  • 사이클 방지를 위해 같은 집합에 포함되어있는지 확인이 필요하므로 Union-Find 알고리즘을 사용했다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private 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));
        StringBuilder sb = new StringBuilder();
        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;
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>();

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            pq.add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken())));
        }

        int sum = 0;
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();

            if (union(edge.start, edge.end)) {
                sum += edge.cost;
            }
        }

        bw.write(Integer.toString(sum));
        bw.flush();
    }

    private static boolean union(int a, int b) {
        int ap = find(a);
        int bp = find(b);

        if (parent[ap] == parent[bp]) {
            return false;
        } else {
            parent[bp] = parent[ap];
            return true;
        }
    }

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

    private static class Edge implements Comparable<Edge> {
        int start, end, cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

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

🔸 코드 해석 🔸

• 간선의 정보를 저장하고, 우선순위 큐에서 정렬하기 위해 Edge 클래스를 만들어 사용했다.
• Union-Find 알고리즘을 위해 union과 find 메서드를 사용해 구현했다.
• 우선순위 큐에 원소가 남지 않을 때 까지 계산을 반복한다.
  • 같은 집합이 아니라면, 하나의 집합으로 합쳐주고 가중치를 누적한다.
• 최종 누적된 가중치를 출력한다.

---

🔸 end 🔸

•  오랜만에 MST 문제를 풀어보았는데 크루스칼 알고리즘에 우선순위 큐가 적용되는건 기억했지만, Union-Find가 사용되는게 기억 안나서 알고리즘 설명을 다시 읽어보았다.
  • MST 관련 문제를 더 연습할 필요가 있을 것 같고, 다음엔 Prim 알고리즘을 사용해봐야겠다.