백준 1197 - 최소 스패닝 트리

문제

https://www.acmicpc.net/problem/1197

풀이

• 전형적인 MST를 활용해 풀이하는 문제
• 유니온 파인드를 활용한 크루스칼 알고리즘을 이용하여 풀이했으며 로직의 전개 과정은 다음과 같다.
  1. 연결하는 두 정점 번호, 간선 비용을 담은 Edge 클래스 정의
  2. 유니온 파인드를 위한 parent 배열 선언, V 크기로 초기화
     • parent 배열은 음수일 때 랭크, 양수일 때 부모 정점 번호 의미
  3. 간선 비용 최소힙 정의, 간선 정보를 입력 받으며 힙에 저장
  4. 힙에서 V-1개의 간선 채택
     • find 연산을 통해 연결된 두 정점의 루트 정점 탐색
     • 두 루트 정점이 다를 경우 union 연산 수행하며 간선 채택
     • 채택한 간선 개수 증가, 총 간선 비용에 누적
• 로직의 시간 복잡도는 크루스칼의 $O(ElogE)$로 수렴, 최대인 $E=100,000$인 경우에도 1초 제한 조건 무난히 통과

코드

import static java.lang.Integer.parseInt;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = parseInt(st.nextToken());
        int E = parseInt(st.nextToken());

        parent = new int[V];
        Arrays.fill(parent, -1);

        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingLong(e -> e.w));
        while (E-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken()) - 1;
            int v = parseInt(st.nextToken()) - 1;
            int w = parseInt(st.nextToken());

            pq.offer(new Edge(u, v, w));
        }

        int count = 0;
        int sum = 0;
        while (count < V - 1) {
            Edge e = pq.poll();

            int u = find(e.u);
            int v = find(e.v);
            if (u == v) {
                continue;
            }

            if (parent[u] < parent[v]) {
                parent[u] += parent[v];
                parent[v] = u;
            } else {
                parent[v] += parent[u];
                parent[u] = v;
            }
            count++;
            sum += e.w;
        }

        System.out.println(sum);
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0) {
            return u;
        }

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

    static class Edge {

        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과