[백준] 1197 - 최소 스패닝 트리(Java)

문제 파악

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

풀이

제목에서도 알 수 있지만 최소 신장 트리 MST 문제이다(Minimum Spanning Tree)
BFS, DFS에서는 방문 여부 체크하는 visited 배열을 쓰다가 사이클을 신경 쓰는 문제를 오랜만에 풀어 흥미로웠다..

본론으로 돌아가자면 기본적으로 부모(루트) 노드에 대한 접근이 필요하다.

부모 노드에 대한 정보를 저장하기 위해 부모 노드의 인덱스를 값으로 가지는 일차원 배열(parent[])을 선언하여 사용해 주도록 하자.
여기서 부모 노드가 되는 조건은 parent[i] = i일 때가 된다.
또한 부모 노드가 같은 정점이라면, 같은 트리에 속해있다고도 이해할 수 있다.

위 조건을 염두에 두고 핵심적인 두 가지 기능을 구현하도록 하자.

부모 노드 찾기

부모 노드를 찾기 위한 방법은 재귀적으로 탐색하는 방법을 택했다.
간단하게 부모 노드일 때 까지 탐색하면 된다.
pseudo 코드는 다음과 같다.

f(n) :
if(parent[n] == n) return n;
return f(parent[n]);

트리 병합

자식 노드끼리 연결할 때에도 루트 노드의 parent[] 값을 변경함을 주목하자.

위의 "부모 노드 찾기"를 활용하여 자식 노드의 부모 노드를 탐색하고, 부모의 parent[] 값을 다른 루트의 인덱스로 지정해 주면 두 트리를 연결할 수 있다.

두 트리의 병합

 

두 기능을 모두 구현하였으면, 두 기능을 사용하여 모든 정점을 방문하는 트리의 최소 가중치를 찾도록 하자

주어진 간선을 가중치 오름차순으로 정렬하여 간선을 뽑아 트리를 구성한다.

이때 뽑은 간선으로 구성된 트리가 사이클(순환 구조, 고리)을 가지면 안 된다.
이는 아래 그림과 같이 루트가 같아서는 안 된다는 것을 의미한다.

사이클

따라서 간선을 더할 때마다 사이클을 만들지 않는다면 두 정점을 가지는 트리를 병합해 주도록 한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int V = Integer.parseInt(input[0]);
        int E = Integer.parseInt(input[1]);
        PriorityQueue<Node> queue = new PriorityQueue<>();
        for (int e = 0; e < E; e++) {
            String[] line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]) - 1;
            int b = Integer.parseInt(line[1]) - 1;
            long w = Long.parseLong(line[2]);
            queue.offer(new Node(a, b, w));
        }
        long answer = 0;
        parent = new int[V];
        for (int p = 0; p < V; p++) {
            parent[p] = p;
        }
        int edgeCount = 0;
        while (!queue.isEmpty() && edgeCount < V - 1) {
            Node latest = queue.poll();
            if (findParent(latest.from) == findParent(latest.to)) {
                continue;
            }
            union(latest.from, latest.to);
            answer += latest.weight;
            edgeCount++;
        }
        System.out.println(answer);
    }

    private static void union(int a, int b) {
        int aRoot = findParent(a);
        int bRoot = findParent(b);
        if (aRoot != bRoot) {
            parent[bRoot] = aRoot;
        }
    }

    private static int findParent(int target) {
        if (parent[target] == target) return target;
        parent[target] = findParent(parent[target]); // 관계 정리
        return parent[target];
    }

    static class Node implements Comparable<Node> {
        int from;
        int to;
        long weight;

        public Node(int from, int to, long weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node node) {
            return Long.compare(this.weight, node.weight);
        }
    }
}