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

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

 

MST 기본 문제 (크루스칼 사용함) 

 

가중치 오름차순 정렬된 edges를 순회하며,  V-1개의 간선을 만들면 종료한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

  static class Edge implements Comparable<Edge> {

    int f, t, v;

    Edge(int f, int t, int v) {
      this.f = f;
      this.t = t;
      this.v = v;
    }

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

  static int[] p;

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int ans = 0;
    int e = 0;
    int V = Integer.parseInt(st.nextToken());
    int E = Integer.parseInt(st.nextToken());

    p = new int[V + 1];
    for (int i = 1; i <= V; i++) {
      p[i] = i;
    }

    List<Edge> edges = new ArrayList<>();

    for (int i = 0; i < E; i++) {
      st = new StringTokenizer(br.readLine());
      edges.add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
          Integer.parseInt(st.nextToken())));
    }

    Collections.sort(edges);

    for (Edge edge : edges) {

      if (find(edge.f) == find(edge.t)) {
        continue;
      }

      union(edge.f, edge.t);
      ans += edge.v;
      e++;

      if (e == V - 1) {
        System.out.println(ans);
        return;
      }
    }
  }

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

    if (a < b) {
      p[b] = a;
    } else {
      p[a] = b;
    }
  }

  private static int find(int a) {

    if (p[a] == a) {
      return a;
    }

    return p[a] = find(p[a]);
  }
}