크루스칼 알고리즘

서론

최소 신장 트리를 구하는 알고리즘은 크루스칼 알고리즘에 대해 알아보고 관련된 백준 1197 문제를 풀어보자.

최소 신장 트리에대한 설명은 아래 글을 참고하자.

2024.08.13 - [알고리즘] - 최소 신장 트리

최소 신장 트리

 

크루스칼 알고리즘

최소 신장 트리(이하 MST)를 구하는 크루스칼 알고리즘은 다음과 같은 순서를 가진다.

1. 간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다
2. 현재 선택한 간선이 정점 U,V를 연결하는 간선이라고 할 때, 만약 U,V가 같은 그룹이라면 넘어가고 다른 그룹이라면 같은 그룹으로 만들고 현재 간선을 MST에 추가한다.
3. 최소 신장 트리에 V - 1개의 간선을 추가할때까지 2번 과정을 반복한다.

이해하기 쉽도록 그림을 통해 살펴보자.

 

위와 같은 그래프가 있다고 하자. 정점의 색은 정점이 속한 그룹을 나타낸다. 초기에는 각 정점이 모두 다른 그룹에 속해있다. 

간선의 크기를 오름차순으로 정렬해야하지만 세부 구현은 나중에 보도록 하고 우리는 인간이기에 직관적으로 정렬된 순서를 알 수 있다.

 

1. 우리는 가장 비용이 작은 간선인 1번과 4번 노드를 잇는 가중치가 2인 간선을 선택했다.

2. 1번 노드와 4번 노드는 서로 다른 그룹이다. 이 두개를 같은 그룹으로 만들고 간선을 MST에 추가하자. 

 

 

이제 위와같은 방식을 선택된 간선이 정점의 개수 - 1 이 될때까지 반복하면 된다. 다음으로 가중치가 가장 작은 간선을 뽑아보자. 가중치가 3인 간선이 두개 보인다. 이중 아무거나 상관없다. 여기서는 2와 3을 잇는 가중치 3 간선을 선택해봤다. 

 

1. 가중치가 3인 2번 노드와 3번 노드를 잇는 간선을 선택했다.

2. 2번과 3번 노드는 서로 다른 그룹이다. 이 두개를 같은 그룹으로 만들고 간선을 MST 에 추가한다.

 

 

계속 진행해보자. 다음으로는 가중치가 3인 노드 1과 2를 잇는 간선을 선택했다.

 

1. 가중치가 3인 1번 노드와 2번 노드를 잇는 간선을 선택했다.

2. 노드 1번과 2번은 서로 다른 그룹이다. 이 두개를 같은 그룹으로 만들고 간선을 MST에 추가한다.

 

사실 눈치가 빠른 사람이라면 이전 단계에서도 느꼈겠지만, 이쯤 오니 이해가 안되는게 있다. 우리야 사람이고 눈으로 보고있으니 초록 그룹과 파랑 그룹이 서로 다른 그룹이라는것을 알지만 이 두개가 서로 다른 그룹이라는 것을 어떻게 알 수 있을까? 

 

이 문제를 해결하기 위해서는 Union Find 라는 알고리즘을 이해해야 한다. 아래 잘 정리된 글을 소개하고 이 글에서는 다루지 않겠다. 크루스칼 알고리즘을 효율적으로 구현하기 위해서는 Union Find를 이용해야 한다. 여기서 효율적이라 함은, 여러분의 알고리즘 문제 통과를 의미한다. 읽어보면 많이 복잡하지 않으니 가볍게 읽어보고오도록 하자.

https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)

 

 

 

이제 다음으로는 2번 노드와 5번 노드를 잇는 가중치 4 간선을 선택했다. 

 

1. 2번 노드와 5번 노드를 잇는 가중치 4 간선을 선택했다.

2. 2번 노드와 4번 노드는 서로 다른 그룹이다. 이 두개를 같은 그룹으로 만들고 간선을 MST에 추가한다.

 

이제 선택된 간선이 노드의 개수 - 1 개인 4개가 되었다. 알고리즘을 종료한다. 만들어진 MST는 가중치의 총 합이 12가 된다. 내가 예시로 든 그래프에서는 MST가 이 형태 하나 뿐 이지만, 그래프에 따라 여러 종류가 나올 수 있다. 

 

문제풀이

이제 실제 문제를 풀어보도록 하자. 백준 1197번 문제인 최소 스패닝 트리이다. 

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

 

 

public static ArrayList<Integer[]> edges;

... 중략 ... 

edges = new ArrayList<>();
for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int from = Integer.parseInt(st.nextToken());
    int to = Integer.parseInt(st.nextToken());
    int value = Integer.parseInt(st.nextToken());
    edges.add(new Integer[]{from, to, value});
}
edges.sort((o1, o2) -> o1[2] - o2[2]);

 

간선의 정보는 위와 같이 정의했다. List edges를 정의하고 내부에는 [정점1, 정점2, 가중치] 를 배열로 저장한다. 그 후 가중치를 기준으로 오름차순 정렬을 해 준다.

public static int[] parent;

... 중략 ...

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

 

parent 라는 배열을 초기화 해 주었다. 이건 그룹 판별을 위한 자료구조이다. 자신 노드의 부모 노드를 갖고있다. 초기화는 모두 자기 자신을 할당해주었다. 최초에는 위에서 설명했듯이 모두 각각의 그룹으로 보고 시작하기 때문이다. 

 

for(Integer[] edge : edges) {
    if(SELECTED_EDGE == N - 1) break;

    int node1 = edge[0];
    int node2 = edge[1];
    int value = edge[2];

    if(!isSameGroup(node1, node2)) {
        SELECTED_EDGE++;
        RESULT += value;
    }
}

 

오름차순으로 정렬된 간선들을 순회하며 진행한다. 선택된 간선의 개수가 정점의 개수 - 1 이라면 종료 된다. isSameGroup은 Union Find를 이용해 구현된 같은 그룹인지 파악하는 함수이다. 만약 같은 그룹이 아니라면 선택된 간선의 개수를 늘려주고 결과값에 현재 간선의 가중치를 더해준다. 전체 구현 코드는 아래와 같다.

public class P1197 {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int N,M, SELECTED_EDGE = 0, RESULT = 0;
    public static int[] parent;
    public static ArrayList<Integer[]> edges;
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        edges = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            edges.add(new Integer[]{from, to, value});
        }
        edges.sort((o1, o2) -> o1[2] - o2[2]);

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

        for(Integer[] edge : edges) {
            if(SELECTED_EDGE == N - 1) break;

            int node1 = edge[0];
            int node2 = edge[1];
            int value = edge[2];

            if(!isSameGroup(node1, node2)) {
                SELECTED_EDGE++;
                RESULT += value;
            }
        }

        System.out.println(RESULT);
    }

    public static boolean isSameGroup(int node1, int node2) {
        int p1 = findParent(node1);
        int p2 = findParent(node2);
        if(p1 == p2) return true;
        if(p1 < p2){
            parent[p2] = p1;
        }else{
            parent[p1] = p2;
        }
        return false;
    }

    public static int findParent(int node) {
        if(parent[node] == node) return node;
        return findParent(parent[node]);
    }
}