[알고리즘] 9-7 원더랜드 - 크루스칼 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07

크루스칼 알고리즘(Kruskal Algorithm)

• 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘
• Greedy를 이용하여 가중치 그래프의 모든 정점을 최소 비용을 연결하는 방법을 찾는 것
• 최소 신장 트리 : 가중치 그래프에서 간선의 가중치 값의 합이 최소가 되고, 회로가 없이 모든 정점이 연결되어있는 트리를 뽑아내는 것
• 신장 트리 : 그래프의 모든 정점이 연결되어있고, 회로가 없는 그래프

동작 과정

1. 그래프의 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
2. 오름차순으로 정렬된 리스트에서 간선들을 순서대로 하나씩 뽑는다.(낮은 가중치부터)
3. 뽑은 간선이 회로를 형성하지 않으면 집합에 추가한다. -> union&find 알고리즘을 사용하여 두 정점이 같은 집합에 속하는지 검사하여 회로인지 판단

풀이 코드

//연결된 정점과 간선의 가중치를 나타내는 클래스
class Edge implements Comparable<Edge> {
    int v1;
    int v2;
    int 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;
    }
}

package inflearn.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

//원더랜드(최소 스패닝 트리) - 크루스칼 알고리즘
public class Main9_7_1 {

    //집합을 표현. 배열의 인덱스는 정점 번호, 값은 집합의 번호
    static int[] unf;

    //정점의 집합 번호 반환
    public static int find(int v) {
        if (unf[v] == v)
            return v;
        else
            return unf[v] = find(unf[v]);
    }

    //두 정점을 같은 집합으로
    public static void union(int v1, int v2) {
        int findV1 = find(v1);
        int findV2 = find(v2);

        if (findV1 != findV2)
            unf[findV1] = findV2;
    }

    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()); //도로의 개수
        int sum = 0;

        List<Edge> list = new ArrayList<>(e);
        unf = new int[v + 1];

        //집합 배열 초기화
        for (int i = 1; i <= v; i++) {
            unf[i] = i;
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.add(new Edge(a, b, c));
        }

        //가중치를 기준으로 오름차순으로 정렬
        Collections.sort(list);

        for (int i = 0; i < e; i++) {
            Edge findEdge = list.get(i);

            //두 정점을 연결했을 때 회로를 형성하지 않으면(같은 집합이 아니라면)
            if (find(findEdge.v1) != find(findEdge.v2)) {
                union(findEdge.v1, findEdge.v2);
                sum += findEdge.cost;
            }

        }

        System.out.println(sum);

        br.close();
    }
}