[SWEA] 3124 최소 스패닝 트리 - JAVA

1. 문제 

SW Expert Academy

---

2. 풀이

• result type==> long이다. 타입체크를 잊지 말아야 한다.
• 최소 간선 순으로 합집합하되 싸이클이 생긴다면(find(a)==find(b)) 추가하지 않고 다음 간선으로 넘어간다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class D4_3124_최소스패닝트리 {
   static int[] sets;
   static int[] size;

   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringTokenizer st;
      StringBuilder sb = new StringBuilder();

      for (int tc = 1; tc <= T; tc++) {
         st = new StringTokenizer(in.readLine());
         int V = Integer.parseInt(st.nextToken());
         int E = Integer.parseInt(st.nextToken());

         sets = new int[V+1];
         size = new int[V+1];

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

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

         int n = 0;
         long result = 0;
         while (n!=V-1) {
            int[] graph = pQueue.poll();
            if (!union(graph[0], graph[1])) continue;
            result += graph[2];
            n++;
         }
         sb.append("#").append(tc).append(" ").append(result).append("\n");
      }
      System.out.print(sb);
   }

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

   private static boolean union(int a, int b) {
      int pa = find(a);
      int pb = find(b);

      if (pa == pb) return false;

      if (size[pa] > size[pb]) sets[pb] = pa;
      else if (size[pa] == size[pb]) size[pb]++;

      if (size[pb] > size[pa]) sets[pa] = pb;

      return true;
   }

}

---

3. 결과