[JAVA][BOJ 1197] MST: 최소 스패닝 트리

 

문제링크

문제 파악

최소 스패닝 트리: 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

• 사이클을 포함하면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 스패닝 트리를 구성하는 엣지의 개수는 항상 N-1개다.

정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000), 가중치는 음수일 수도 있으며 절댓값이 1,000,000을 넘지 않는다.

최소 스패닝 트리의 가중치는 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

접근 방법

크루스칼 알고리즘: 엣지 리스트 pq(노드1, 노드2, 가중치), 사이클 확인용 UNION-FIND

class Pair 
	node 1, node 2, weight
	
    // 가중치가 작은 순으로 엣지 리스트 정렬
    @Overrride 
    public int compare(Pair x.weight, Pair y.weight)

// edge list
List<Pair> = new ArrayList<>(); 
또는 pq 사용

// 사이클 존재 확인: union find
boolean find()
union() if find로 찾은 루트가 같다면 return 0;

while ( int 엣지를 더한 횟수 <= V - 1)
	미사용 에지 중 가중치가 작은 에지 선택 -> pq.poll()
    if (find 로 사이클 유무 확인) {
    	continue;
    }
    union();
    엣지 ++ ;

 

코드 구현

import java.util.*;

public class Main {
    public static class Edge implements Comparable<Edge> {
        int s; int e; int v;
        public Edge(int s, int e, int v) {
            this.s = s; this.e = e; this.v = v;
        }

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

    static PriorityQueue<Edge> pq = new PriorityQueue<>();
    static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        pq = new PriorityQueue<>();

        for (int i = 0; i < m; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int v = sc.nextInt();
            pq.add(new Edge(s, e, v));
        }

        parent = new int[n+1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }

        int cnt = 0;
        int ans = 0;
        while ( cnt < n-1) {
            Edge cur = pq.poll();
            if (union(cur.s, cur.e)){
                ans += cur.v;
                cnt++;
            }

        }

        System.out.println(ans);

    }
    public static boolean union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
            return true;
        }
        return false;
    }

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

 

배우게 된 점

범위: while( cnt <=  n-1 ) 때문에 nullPointer 에러가 났다.

내부에서 cnt ++ 하기 때문에 `< n-1`  주의하자