[백준 1647] 도시 분할 계획 - JAVA

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

 

1. MST 구성 (크루스칼 사용)

2. total weight - max weight인 간선을 하나 뺀 값 출력

 

제출 코드

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.Comparator;
import java.util.List;
import java.util.StringTokenizer;

class Main {

  static class Edge {

    int f, t, w;

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

  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 N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

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

    for (int i = 0; i < M; 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, Comparator.comparing(e -> e.w));

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

    int tw = 0;
    int mw = 0;
    int vc = 0;

    for (Edge e : edges) {

      if (find(e.f) != find(e.t)) {
        union(e.f, e.t);
        tw += e.w;
        mw = Math.max(e.w, mw);
        vc++;

        if (vc == N - 1) {
          break;
        }
      }
    }

    System.out.println(tw - mw);
  }

  static int find(int a) {

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

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

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

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

랭크 기반

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.List;
import java.util.StringTokenizer;

class Main {

  static class Edge {

    int f, t, w;

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

  static int[] p, r;

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

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

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

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

    for (int i = 0; i < M; 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, Comparator.comparing(e -> e.w));

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

    int tw = 0;
    int mw = 0;
    int vc = 0;

    for (Edge e : edges) {

      if (find(e.f) != find(e.t)) {
        union(e.f, e.t);
        tw += e.w;
        mw = Math.max(e.w, mw);
        vc++;

        if (vc == N - 1) {
          break;
        }
      }
    }

    System.out.println(tw - mw);
  }

  static int find(int a) {

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

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

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

    if (a == b) {
      return;
    }

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