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

✉️문제

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

1197번: 최소 스패닝 트리

 

📝 접근

최소 스패닝 트리를 구하는 문제이다. 최소 스패닝 트리를 구하는 방법은 2가지이다.

1. 크루스칼 알고리즘

2. 프림 알고리즘

 

이번 문제에서는 크루스칼 알고리즘을 이용하였다. 구현 방법은 다음과 같다.

1. Edge라는 클래스를 만들어 cost를 기준으로 오름차순 정렬한다.

2. List를 순회하면서 연결되지 않은 간선을 연결한다. 이때 간선을 연결함으로써 순환구조가 생기지 않도록 만들어야 한다.

3. 이를 위해 Union&Find 알고리즘을 추가로 이용한다. 

 

🗝 문제풀이

package step2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Q1197 {

    static int[] unf; // Union&Find를 위한 배열

    public static class Edge implements Comparable<Edge> {
        int v1, v2, cost;

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

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int v = sc.nextInt(); // 정점의 개수
        int e = sc.nextInt(); // 간선의 개수

        unf = new int[v+1];
        for(int i = 0; i <= v; i++) {
            unf[i] = i;
        }
        
        // 입력 받기
        ArrayList<Edge> list = new ArrayList<>();
        for(int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            list.add(new Edge(a, b, c));
        }

		// 오름차순 정렬
        Collections.sort(list);

        int answer = 0;
        for (Edge edge : list) {
            int v1 = find(edge.v1);
            int v2 = find(edge.v2);
            
            // 만약에 간선을 연결해도 순환구조가 생기지 않으면 이를 연결한다.
            if(v1 != v2) {
                answer += edge.cost;
                union(v1, v2);
            }
        }
        System.out.println(answer);
    }

	// Union&Find 
    public static int find(int v){
        if(unf[v] == v) return v;
        else return unf[v] = find(unf[v]);
    }

    public static void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) unf[fa] = fb;
    }
}

 

[최적화?]

트리 구조에서는 간선의 개수 = 정점의 개수 - 1  의 특징을 가진다. 이를 이용하기 위해 count 변수를 이용하여 조건이 만족하면 반복문을 탈출할 수 있도록 작성해보았다.

 

첫 번째가 count 변수를 이용했을 때, 두 번째가 count 변수를 이용하지 않았을 때이다. 차이가 크지 않았다...