[문제풀이] 09-07. 원더 랜드(크루스칼)

인프런, 자바(Java) 알고리즘 문제풀이

Greedy Alogorithm - 0907. 원더 랜드(크루스칼, 최소 신장 트리)

---

🗒️ 문제

---

🎈 나의 풀이

	private static List<Edge> list = new ArrayList<>();
    private static int[] arr;

    private static class Edge implements Comparable<Edge> {
        int vet1, vet2, cost;

        public Edge(int vet1, int vet2, int cost) {
            this.vet1 = vet1;
            this.vet2 = vet2;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }

    private static int find(int a) {
        if(arr[a] == a) return a;
        return arr[a] = find(arr[a]);
    }

    private static void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);

        if(fa != fb) arr[fa] = fb;
    }

    private static int solution() {
        int answer = 0;

        Collections.sort(list);

        for(Edge e : list) {
            if(find(e.vet1) != find(e.vet2)) {
                union(e.vet1, e.vet2);
                answer += e.cost;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        arr = new int[n+1];

        for(int i=0; i<=n; i++) arr[i] = i;

        for(int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

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

        System.out.println(solution());
    }

---

🖍️ 강의 풀이

  class Edge implements Comparable<Edge>{
      public int v1;
      public int v2;
      public int cost;
      Edge(int v1, int v2, int cost) {
          this.v1 = v1;
          this.v2 = v2;
          this.cost = cost;
      }
      @Override
      public int compareTo(Edge ob){
          return this.cost-ob.cost;
      }
  }

  class Main {
      static int[] unf;
      public static int Find(int v){
          if(v==unf[v]) return v;
          else return unf[v]=Find(unf[v]);
      }
      public static void Union(int a, int b){
          int fa=Find(a);
          int fb=Find(b);
          if(fa!=fb) unf[fa]=fb;
      }
      public static void main(String[] args){
          Scanner kb = new Scanner(System.in);
          int n=kb.nextInt();
          int m=kb.nextInt();
          unf=new int[n+1];
          ArrayList<Edge> arr=new ArrayList<>();
          for(int i=1; i<=n; i++) unf[i]=i;
          for(int i=0; i<m; i++){
              int a=kb.nextInt();
              int b=kb.nextInt();
              int c=kb.nextInt();
              arr.add(new Edge(a, b, c));
          }
          int answer=0;
          Collections.sort(arr);
          for(Edge ob : arr){
              int fv1=Find(ob.v1);
              int fv2=Find(ob.v2);
              if(fv1!=fv2){
                  answer+=ob.cost;
                  Union(ob.v1, ob.v2);
              }
          }
          System.out.println(answer);
      }
  }

---

💬 짚어가기

해당 문제는 그래프의 최소 신장 트리를 구하는 문제이다.

▶︎ 신장 트리(Spanning Tree)
신장 트리는 그래프 내에 있는 모든 정점을 연결하며, 사이클이 없는 그래프를 의미한다.
$n$개 정점을 갖는 신장 트리의 간선 수는 $n-1$개이다.

▶︎ 최소 신장 트리(Minimun Spanning Tree)
최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리이다.
가중치는 거리, 비용, 시간 등 여러가지로 응용할 수 있다.

최소 신장 트리의 대표적인 알고리즘으로 프림(Prim)과 크루스칼(Kruskal)이 있다
이번 풀이에서는 크루스칼 알고리즘에 대해 알아보겠다.
( 프림 알고리즘 풀이 ☛ 원더 랜드(프림) )

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

1. 간선 정렬
   주어진 그래프의 모든 간선에 대해서 가중치가 낮은 순으로 오름차순 정렬한다.

2. 간선 합치기
   정렬된 간선을 순서대로 선택하며 간선의 두 정점을 Union 한다.
   만약 선택된 두 정점이 같은 집합에 속해있다면, 해당 간선을 포함시키지 않는다.
   (트리에 사이클이 생기는 것을 방지)

크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다.
아래와 같은 매커니즘으로 선택된 간선들을 연결하여 최소 비용 신장트리를 만든다.

⏱️ 시간 복잡도 : $O(E$ $logV)$

간선의 수를 $E$(Edge), 노드의 수를 $V$(Vertex)라고 했을 때,

모든 정점을 독립적인 집합으로 만드는 과정 : $O(E)$
그래프의 모든 간선을 가중치 기준으로 오름차순 정렬 : $O(logE)$
2개 부분집합 각각의 루트 노드를 확인(find)하고 서로 다른 경우 Union : $O(1)$

$O(E$ $logE)$의 시간 복잡도를 갖는다.

이때, 중복 간선을 포함하지 않는 경우 간선의 개수는 항상 (노드의 개수)$^2$ 이하이다.
( 간선의 최대 개수 : 모든 노드가 연결 되어 있는 경우인 $V * (V-1)$ )

$logE$는 $log(V^2)$보다 작고, $log(V^2)$은 $2logV$와 같으므로, $O(logV)$로 표현할 수 있다.
따라서, 크루스칼 알고리즘의 시간 복잡도를 $O(E$ $logV)$로 표현할 수 있다.

✔️ 코드 구현 살펴보기
위 과정을 작성된 코드와 비교하여 설명하면 다음과 같다. (강의 코드 참고)

Edge 클래스는 간선을 나타내며, v1과 v2는 간선의 두 끝을, cost는 가중치를
나타낸다.Comparable 인터페이스를 구현하여 가중치에 따라 정렬할 수 있도록 한다.

Find 함수는 주어진 정점의 부모(루트)를 찾는 함수이다. 경로 압축(Path Compression)을
사용하여 루트를 찾을 때마다 해당 정점의 부모를 루트로 갱신한다.
(각 정점의 부모(루트)를 저장할 수 있는 배열 unf을 생성한다.)

Union 함수는 두 개의 집합을 합치는 함수이다. 각 집합의 루트를 찾아서 연결한다.

1. 간선 정렬
   입력 받은 간선을 Edge 객체를 생성하여 리스트 arr에 담고,
   Collections.sort를 사용하여 간선들을 가중치 순으로 정렬합니다.

2. 간선 합치기
   정렬된 간선들을 순회하면서, 간선의 양 끝점이 서로 다른 집합에 속해 있으면 두 집합을 합치고
   해당 간선의 가중치를 최종 결과에 더합니다.

3. 결과 출력
   최소 비용 신장 트리의 가중치 합인 answer를 출력합니다.