[JAVA] 백준 1197 스패닝 트리

 

 

 

1197번: 최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

풀이

📌 유니온 파인드

    static void union(int a, int b){
        int x = find(a);
        int y = find(b);

        A[y] = x;
    }

    static int find(int a){
        if(A[a] == a) return a;
        else{
            A[a] = find(A[a]);
            return A[a];
        }
    }

find : 현재 정점이 어떤 집합에 속하는지 재귀적으로 찾습니다.

union : 두 정점을 하나에 집합에 속하도록 합니다.

📌 최소 신장 트리 구성

        PriorityQueue<Edge> edges = new PriorityQueue<>((o1, o2) -> o1.weight- o2.weight);
        A = new int[N];

        for(int i=1; i<N; i++){
            A[i] = i;
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            edges.offer(new Edge(a, b, w));
        }

        int answer = 0;
        while (!edges.isEmpty()){
            Edge e = edges.poll();
            if(find(e.start) != find(e.destination)){
                union(e.start, e.destination);
                answer += e.weight;
            }
        }

edges : 우선순위 큐를 사용하여 가중치가 낮은 간선부터 차례로 정렬하였습니다.

A : 유니온-파인드를 사용하여 집합을 나타내기 위한 배열입니다.

우선순위 큐에서 낮은 가중치를 가진 간선부터 차례로 선택하면서, 선택된 간선의 출발지와 목적지가 다른 집합에 속하는지 체크하고 만약 다른 집합에 속한다면 해당 간선을 선택해서 가중치를 더해주었습니다.

📌 전체 코드

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

class Main {
    static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken())+1;
        int M = Integer.parseInt(st.nextToken());

        PriorityQueue<Edge> edges = new PriorityQueue<>((o1, o2) -> o1.weight- o2.weight);
        A = new int[N];

        for(int i=1; i<N; i++){
            A[i] = i;
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            edges.offer(new Edge(a, b, w));
        }

        int answer = 0;
        while (!edges.isEmpty()){
            Edge e = edges.poll();
            if(find(e.start) != find(e.destination)){
                union(e.start, e.destination);
                answer += e.weight;
            }
        }
        System.out.println(answer);
    }

    static void union(int a, int b){
        int x = find(a);
        int y = find(b);

        A[y] = x;
    }

    static int find(int a){
        if(A[a] == a) return a;
        else{
            A[a] = find(A[a]);
            return A[a];
        }
    }

    static class Edge{
        int start;
        int destination;
        int weight;

        Edge(int start, int destination, int weight){
            this.start = start;
            this.destination = destination;
            this.weight = weight;
        }

    }

}

결과