자바(Java) 알고리즘 문제풀이 최소 스패닝 트리[백준 / 크루스칼(그리디)]

출처 - 구글 이미지

 

 

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

1197번: 최소 스패닝 트리

 

 

---

 

 

풀이 코드

이 문제는 최소 신장트리를 구하는 문제인데, 크루스칼 알고리즘을 사용하면 해결되는 문제이다.

크루스칼 알고리즘이란, 그래프 내 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다. 쉽게 말해 그래프를 회로가 없는 트리로

만들면 되는 것.

그래프 내의 모든 정점들 중, 가장 적은 비용을 가진 간선부터 연결을 시작하고 연결하기 전에 해당 간선이 사이클에 포함되어있는지 ?

포함되어 있다면 가중치를 더하지 말고 포함되어 있지 않다면 집합에 포함되어 있지 않으므로 가중치를 더하면 된다.

 

사이클(집합)에 포함되어 있는지, 아닌지 어떻게 구분할 수 있을까 ? 이럴 때 사용할 수 있는게 Union-FInd 자료구조이다.

서로소 집합을 표현하는 자료구조로 직접 구현을 통해 Union(), FInd() 메서드를 만들고 노드를 Find() 의 인자로 보낸 뒤 집합을 추려내

집합에 포함되어 있는지 아닌지를 판단할 수 있다.

 

최소 신장트리를 구현하기 위한 진행을 요약해보자면,

1. 최소 간선 비용을 찾기 위해 간선 비용을 기준으로 오름차순 정렬한다.

2. 간선을 하나씩 확인하면서 사이클이 발생하는지 확인한다. (FInd 메서드 활용)

2-1. 사이클이 발생하지 않는 간선이라면 신장트리에 포함시킨다. (Union 메서드 활용)

2-2. 사이클이 발생한다면 신장트리에 포함시키지 않는다.

 

먼저 Union-Find 메서드 먼저 구현해보자.

union() 는 집합을 만들어주는 메서드, find() 는 인자로 들어온 노드의 부모 노드를 찾아 반환해주는 메서드이다.

int[] unf = new int[노드갯수 + 1];

void union(int v1, int v2) {
	int fa = find(v1);
    int fb = find(v2);
    if(fa != fb) unf[fa] = fb; 
}

int find() {
	if (v == unf[v]) return unf[v];
    else return unf[v] = find(unf[v]);
}

 

 

이제 Union-Find 자료구조를 구현했으니 크루스칼 알고리즘을 통해 최소 신장(스패닝) 트리를 구현해보자.

 

Edge 에서는 간선 비용을 기준으로 오름차순 정렬을 할 수 있도록 compareTo() 를 재정의한다.

 

노드가 1 부터 시작하므로 unf 배열을 선언할 때, node + 1 만큼의 길이로 선언한다.

선언된 unf 배열의 인덱스는 노드의 번호가 되고, 이 인덱스에 부모 노드가 값으로 들어가는데, 아직은 노드끼리 연결되어 있지 않기 때문에

부모(루트) 노드가 없는 상태이다. 따라서 for 반복을 통해 자기 자신이 부모가 되도록 배열의 값을 셋팅한다.

 

받아오는 한 쌍의 노드만큼 for 반복을 통해 새로운 Edge 객체를 만들고 미리 만들어둔 List 에 추가한다.

 

이제 Edge 리스트만큼 반복하면서 해당 Edge 객체의 한 쌍의 노드가 같은 집합인지 ? (사이클인지) 아닌지 구분한다.

같은 집합이 아니라면 부모 노드가 같지 않으므로 해당 간선의 cost 를 answer 에 더해주면 끝 !

package baekjoongold;

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;

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;
    }

    // cost 기준 오름차순 정렬
    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }
}

public class Boj1197 {
    static int[] unf;

    static void Union(int a, int b) {
        int fa = Find(a);
        int fb = Find(b);
        if (fa != fb) unf[fa] = fb;
    }

    static int Find(int v) {
        if(unf[v] == v) return unf[v];
        else return unf[v] = Find(unf[v]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        List<Edge> list = new ArrayList<>();

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        unf = new int[v + 1];

        for (int i = 1; i <= v; i++) {
            unf[i] = i;
        }

        for (int i = 0; i < e; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st2.nextToken());
            int v2 = Integer.parseInt(st2.nextToken());
            int cost = Integer.parseInt(st2.nextToken());
            list.add(new Edge(v1, v2, cost));
        }

        Collections.sort(list);

        int answer = 0;
        for (Edge edge : list) {
            if (Find(edge.v1) != Find(edge.v2)) {
                answer += edge.cost;
                Union(edge.v1, edge.v2);
            }
        }

        System.out.println(answer);

    }
}