백준 - 1922 네트워크 연결(feat. 크루스칼 알고리즘)

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

1922번: 네트워크 연결

 

 

 

 

---

풀이 방법

내가 무식해서 때문에 용감해져서 도전했던 문제ㅠ.ㅠ

사실 그래프 문제고 탐색하는 문제이기 때문에 DFS 나 BFS 로 하면 되는 문제겠네 하면서 풀었는데

당연히 다르게 푸는 문제였고, 메모리 초과만 5번은 뜬 것 같다.

2시간쯤 지나서 뭔가 이상하다고 느꼈고, 찾아보니 DFS 도 아니고, BFS 도 아니고 크루스칼 알고리즘과 이를 위한 union-find 구현을 통해 푸는 문제라는것을 알았다.

오늘도 새로운 것을 알아간다ㅋㅋㅋㅋ

 

이 문제는 최소 신장 트리를 찾는 문제이고, 이를 위한 알고리즘인 크루스칼과 union-find 를 통해서 답을 찾는 문제이다. 이를 위해서 개념부터 잡고 가겠다.

---

신장 트리

신장 트리란 그래프에서 일부 간선만 사용하면서 모든 노드를 포함하고, 사이클(반복)이 존재하지 않는 부분 그래프를 의미한다.

즉 최소 연결로 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 트리이다.

 

최소 신장 트리

말 그대로 신장 트리의  '비용 최소' 버전이다. 즉 신장트리의 조건인 일부 간선만 사용하며, 모든 노드가 연결되어야하며, 사이클이 없어야하고 동시에 최소한의 비용으로 만들어진 트리를 의미한다.

쉽게 이야기하자면 최소 비용으로 만들어지는 그래프를 구하는 것!

최소 신장 트리 // 출처 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

 

크루스칼 알고리즘 : 유니온-파인드(union - find)

크루스칼 알고리즘은 최소 신장 트리를 찾는 알고리즘 중 하나이다. 그리디 알고리즘의 일종이며 주로 find-union 메서드 구현을 통해 코드를 만든다.

유니온 파인드는 크루스칼 알고리즘의 탐색 방법에 맞춰 union(합치기) 과 find(검색) 메서드를 구현하는 것이다.

즉, 아래와 같은 순서로 동작하는 것이다!

# 크루스칼 알고리즘 
1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다 
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다 
- 사이클이 있는 경우 최소 신장 트리에 포함시키지 않는다.
- 사이클이 없는 경우 최소 신장 트리에 포함시키게 된다
3. 모든 간선에 대하여 2번 과정을 반복한다.

# 크루스칼 알고리즘에 따른 union && find 메서드 구현
1. 오름차순으로 정렬 ==> sort 활용
2. 사이클 발생 유무 확인 => find 메서드를 활용해서 공통 부모 노드 탐색
3. 합치기여부 :
- 2번에서 확인한 결과에 따라 공통 부모 노드가 존재한다면 사이클 발생 -> 공통 부모가 존재한다는 것은 결국 사이클이 발생한다는 것이다. 1-3, 2-3, 3-1 간선이 있을 때 1-3, 2-3 을 연결했다면 3-1 간선은 최소 신장 트리에 포함할 필요가 없다. 이는 3-1의 부모 노드를 찾아서 계산하다보면 결국 3 이 되고, 1-3, 2-3 의 부모 노드 역시 3 이 되기 때문에 사이클이 발생한다고 판단하고, union 메서드를 실행하지 않는다.
- 2번에서 혹인한 결과에 따라 공통 부모 노드가 없다면 사이클이 발생하지 X ->
union 을 실행하고 최소 신장 트리에 포함시킨다.

## 포인트 : 이것만 기억하자!!
결국 크루스칼 알고리즘의 포인트는 간선 데이터의 오름차순 정렬과 공통된 부모 노드의 여부이다. 오름차순으로 정렬하는 것은 최소값을 보다 빨리 찾기 위함이고, 공통된 부모 노드는 노드들의 사이클 여부를 판단하기 위함이다. 사실 요것 두가지만 한다면 크게 어려운 점은 없는 알고리즘이다 => 오히려 코드 구현은 간단한 편이다.

 

나머지는 코드 주석 확인!

package baekJoon;

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

public class Quiz_1922 {
    static int n, m;
    static int[] parent; // 부모 노드
    static ArrayList<Computer> arr = new ArrayList<Computer>();

    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        // 부모 노드 : 기본값을 자기 자신을 초기화
        parent = new int[n + 1];
        for (int i = 1; i < parent.length; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < m; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            arr.add(new Computer(from, to, cost));
        }

        Collections.sort(arr, new Comparator<Computer>() {

            // Compartor 를 사용해 cost 오름차순으로 정렬
            @Override
            public int compare(Computer o1, Computer o2) {
                return o1.cost - o2.cost;
            }
        });

        // 정렬된 arr 에서 하나씩 꺼내서 find 와 union 을 실행한다.
        for (Computer c : arr) {

            // find 에서 부모 노드가 다르게 나온 경우만 => 사이클이 없는 경우만
            // result 에 + 한다 => 최소 신장 트리에 추가한다.
            if (find(c.from) != find(c.to)) {
                union(c.from, c.to);
                result += c.cost;
            }
        }

        System.out.println(result);

    }


    // 부모 노드 찾기 메서드 => find
    static int find(int index) {
        // parent[index] == index 인 경우는 어떤 노드와도 연결되어있지 않은 상태임으로
        // 자기 자신 index 를 return
        if (parent[index] == index) {
            return index;
        }
        // 아니면 find 를 통해서 부모 노드를 return
        return parent[index] = find(parent[index]);
    }

    // 합치기(병합) 메서드 => union
    static void union(int from, int to) {
        // from 과 to 의 부모 노드 확인
        from = find(from);
        to = find(to);

        // find 메서드 실행 후 더 높은 값으로 부모 노드 설정
        // 즉, 작은쪽의 부모 노드 값을 큰 쪽의 부모 노드 값으로 변경
        // 예를 들어 1 - 3 이 있다면
        // 1 의 부모노드는 3, 3의 부모노드는 3 이 되는 것이다.
        if (from > to) {
            parent[to] = from;
        } else {
            parent[from] = to;
        }
    }
}

class Computer {
    int from;
    int to;
    int cost;

    Computer(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }


}

 

- Reference

https://www.youtube.com/watch?v=Gj7s-Nrt1xE 

 

 

https://chanhuiseok.github.io/posts/algo-33/

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)

 

https://loosie.tistory.com/159

[알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java)

 

https://hanyeop.tistory.com/397

[백준] 1922. 네트워크 연결 (Java)

 

https://bangu4.tistory.com/314

[백준 1922] 네트워크 연결 - Java코드 (크루스칼)