[BOJ] 1197 : 최소 스패닝 트리(Java)

문제 링크

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

1197번: 최소 스패닝 트리

---

💡 풀이

문제는 간단하게 최소 스패닝(신장) 트리(MST)를 구하는 문제입니다. 

최소 신장 트리 (MST)

먼저, MST에 간단히 말해보자면, 

그래프의 모든 정점을 사이클 없이 잇는(신장 트리)트리에서 간선의 가중치의 합이 최소가 되는 트리

입니다. 

이를 구하는 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 있지만, 저는 크루스칼 알고리즘을 사용했습니다. 

크루스칼 알고리즘

간선 중심으로 최소 신장 트리를 구하는 알고리즘

다음과 같은 순서로 진행됩니다. 

1. 간선들을 오름차순으로 정렬해 가장 작은 간선 선택
2. 해당 간선이 지금까지 만들어진 MST와 사이클을 형성한다면 제외시키기. 아니라면 추가
3. 모든 간선들에 대해 위 과정을 반복

코드 설명

 node1과 node2의 가중치 값이 입력으로 주어지기 때문에 이 필드로 이루어진 클래스를 하나 생성합니다. 이때 가중치를 기준으로 오름차순 정렬할 필요가 있기 때문에 Comparable의 compareTo 메서드를 구현해줍니다. 

static class Edge implements Comparable<Edge>{
        int v1;
        int v2;
        int weight;

        Edge (int v1, int v2, int weight) {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }

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

그리고, 간선들을 합치기 위한 union, find 메서드를 구현합니다. 

find (int node)

find 메서드는 파마리터로 들어온 node가 어느 그래프에 속하는지 확인하는 메서드로, node의 부모 노드를 반환합니다. 

static int find(int x) {
    if(parent[x] == x)
        return x;

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

union (int node1, int node2)

union 메서드는 파리미터로 넘어온 node1과 node2를 같은 그래프로 합치기 위한 메서드입니다. 이를 위해 먼저 node1과 node2의 부모를 찾는 과정을 거칩니다. 만약 두 부모가 다르다면, node2의 부모를 node1로 바꿈으로써 같은 부모로 합칠 수 있습니다. 

static void union(int v1, int v2) {
    v1 = find(v1);
    v2 = find(v2);

    if (v1 != v2) {
        parent[v2] = v1;
    }
}

 

입력 값들은 가중치를 기준으로 오름차순으로 정렬하기 위해 우선순위 큐를 사용했습니다. 

입력이 끝났다면, 우선순위 큐에서 원소들을 하나씩 poll 하며 만약, 두 노드의 부모가 같다면 넘어가고 같지 않다면 가중치를 더해주고 union 해주는 방식으로 해결할 수 있습니다. 

 

전체 코드

전체적인 코드는 다음과 같습니다. 

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

public class Q1197 {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 + 1; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            pq.offer(new Edge(v1, v2, weight));
        }

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

            if (!isSameParent(find(edge.v1), find(edge.v2))) {
                result += edge.weight;
                union(edge.v1, edge.v2);
            }
        }

        System.out.println(result);
    }


    static void union(int v1, int v2) {
        v1 = find(v1);
        v2 = find(v2);

        if (v1 != v2) {
            parent[v2] = v1;
        }
    }

    static int find(int x) {
        if(parent[x] == x)
            return x;

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

    static boolean isSameParent(int v1, int v2) {
        return find(v1) == find(v2);
    }

    static class Edge implements Comparable<Edge>{
        int v1;
        int v2;
        int weight;

        Edge (int v1, int v2, int weight) {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }

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