[Algorithm] 도시 분할 계획

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 머리를 맞대고 회의 중이었다.

 

마을은 N개의 집과 그 집을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.

 

마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

 

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

 

입력 조건

첫째 줄에 집의 개수 N과 길의 개수 M이 주어진다.

두번째 줄부터 M+1번째 줄까지 길의 정보가 A, B, C 형태로 주어진다. (A번 집과 B번 집을 연결하는 길의 유지비가 C)

 

출력 조건

첫째 줄에 길을 없애고 남은 유지비 합의 최소값을 출력한다.

 

풀이

먼저, N개의 집 가운데 최소한의 비용으로 최소한의 길들을 유지하는 것을 생각한다면

최소신장트리와 같은 형태로 생각할 수 있다. (집-노드, 길-간선)

 

이 때, 마을을 2개로 분할할 계획인 것을 생각하면, 최소신장트리 2개를 만드는 것이라고 볼 수 있다.

먼저 크루스칼 알고리즘을 통해 최소신장트리를 만들고, 가장 비용이 많이 들어가는 길 하나 제거 한다.

 

import java.util.*;

class Edge implements Comparable<Edge> {
  private int nodeA;
  private int nodeB;
  private int expense;

  public Edge (int nodeA, int nodeB, int expense) {
    this.nodeA = nodeA;
    this.nodeB = nodeB;
    this.expense = expense;
  }

  public int getNodeA() {
    return this.nodeA;
  }
  
  public int getNodeB() {
    return this.nodeB;
  }

  public int getExpense() {
    return this.expense;
  }

  public int compareTo(Edge other) {
    if (expense < other.getExpense()) {
      return -1;
    }
    return 1;
  }
}

class Main {

  public static int n, m;
  public static List<Edge> edges = new ArrayList<>();
  public static int[] parent = new int[100001];

  public static int findParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);
  }

  public static void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
  }

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

    for (int i = 0; i <= n; i++) {
      parent[i] = i;
    }

    for (int i = 0; i < m; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = sc.nextInt();
      edges.add(new Edge(a, b, c));
    }

    // 최소 비용부터 앞에 오도록 정렬
    Collections.sort(edges);

    int result = 0;
    // 2개의 도시로 나눠야 하기 때문에 가장 비싼 비용의 길은 제거
    int maxExpense = 0; 
    for (int i = 0; i < edges.size(); i++) {
      int a = edges.get(i).getNodeA();
      int b = edges.get(i).getNodeB();
      int e = edges.get(i).getExpense();
      // 적은 비용의 길부터 이어지지 않았다면
      if (findParent(a) != findParent(b)) {
        // 잇고, 비용 추가
        unionParent(a, b);
        result += e;
        maxExpense = e;
      }
    }

    System.out.println(result - maxExpense);

  } // end main
}