[BOJ] 1197 최소 스패닝 트리 - JAVA

1. 문제

1197번: 최소 스패닝 트리

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

---

2. 풀이

유니온 파인드를 이용해서 크루스칼 알고리즘을 구현했다.

간선의 가중치 순으로 정렬해서, 그 간선을 그래프에 추가할 수 있다면(사이클이 일어나지 않는다면) 합치고 answer에 가중치를 더한다.

import java.io.*;
import java.util.*;

public class BOJ_1197_최소스패닝트리 {
   static int[] root;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int V = Integer.parseInt(st.nextToken());
      int E = Integer.parseInt(st.nextToken());

      root = new int[V+1];
      for(int i=1;i<=V;i++) root[i] = i;

      PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[2]-o2[2]);
      int a,b,c;
      for(int i=0;i<E;i++){
         st = new StringTokenizer(in.readLine());
         a = Integer.parseInt(st.nextToken());
         b = Integer.parseInt(st.nextToken());
         c = Integer.parseInt(st.nextToken());
         pq.offer(new int[]{a,b,c});
      }

      int answer = 0;
      while(!pq.isEmpty()){
         a = find(pq.peek()[0]);
         b = find(pq.peek()[1]);
         c = pq.poll()[2];

         if(a == b) continue;

         union(a,b);
         answer += c;
      }

      System.out.println(answer);
   }

   private static int find(int x){
      if(root[x]==x) return x;
      return root[x] = find(root[x]);
   }

   private static void union(int a,int b){
      int ra = find(a);
      int rb = find(b);
      if(ra==rb) return;

      root[ra] = rb;
   }
}

---

3. 결과

우선순위 큐 사용 - 리스트 사용 - 리스트 사용 - 우선순위 큐 사용

이런 식으로 방식을 바꿔봤는데 큰 차이는 나지 않았다.