🔍 Problem

백준 1197 최소 스패닝 트리

---

📃 Input&Output

---

🌁 문제 배경

가. 문제 설명
최소 스패닝 트리의 가중치 합을 구하는 문제이다.

나. 접근 방법
우선순위 큐를 사용하여 모든 간선을 넣고 가중치가 작은 간선부터 하나씩 빼서 이어주며 해결하였다.

다. 사용할 알고리즘 선택
MST

MST란?

---

📒 수도 코드

가. 모든 간선을 우선 순위 큐에 넣는다.

나. 큐가 빌때까지 다음을 반복한다.
1. 큐에서 간선을 꺼낸다.
2. 그 간선에 붙어있는 양쪽 노드의 부모가 같지 않으면 (=사이클이 존재하지 않으면)
3. 그 두 노드를 연결한다. (Union)
4, 연결된 두 노드의 가중치를 가중치 합에 더해준다.

---

💻 Code

import java.util.*;
import java.io.*;

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


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

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


    public static void main(String args[]) {


        Scanner sc = new Scanner(System.in);

        int V, E;
        long w_sum = 0;
        PriorityQueue<Edge> que = new PriorityQueue<>();
        int[] parent;

        V = sc.nextInt();
        E = sc.nextInt();

        parent = new int[V + 1];
        for (int i = 1; i < parent.length; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < E; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int weight = sc.nextInt();
            que.add(new Edge(v1, v2, weight));
        }

        while (!que.isEmpty()) {
            Edge e = que.poll();

            if (find(parent, e.v1) != find(parent, e.v2)) {
                union(parent, e.v1, e.v2);
                w_sum += e.weight;
            }
        }


        System.out.println(w_sum);
    }

    static int find(int[] parent, int v) {
        if (parent[v] == v) {
            return v;
        }
        return parent[v] = find(parent, parent[v]);
    }

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

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

---

🎸 기타

가. implements Comparable<Class명>
해당 코드를 붙이면, 즉 인터페이스를 상속시키면 해당 클래스를 비교가능한 객체로 만들어준다. 그리고 아래 함수를 오버라이딩 해주면 원하는 비교방법을 선택할 수 있다.

참고로, 최소힙을 구현하고 싶을 때는 아래와 같이 해주면 된다.

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

• compareTo() : return 값이 음수이면 this와 e를 바꾼다. 양수면 그대로 납둔다.

필자는 우선순위 큐를 최소힙으로 만들기 위해 해당 값이 음수일시, 즉 비교하고자 하는 값(this)이 비교대상(원래 큐에 있던 값)보다 작을 시 바꿔주어 힙의 맨 꼭대기로 올리는 형식으로 최소힙을 구현하였다.

---

🤔 느낀점

메모리를 생각보다 많이 차지하는 것 같아서 다음에는 프림 알고리즘으로 구현된 MST로 풀어봐야겠다.