우매함의 봉우리를 넘어서며 개발하면서 기록하기

백준 1647. 도시 분할 계획

23 Mar 2021

문제 바로가기

도시 분할 계획

문제 요약

마을에 N개의 집과 그 집을 연결하는 M개의 길이 있다. 길은 유지하는데 유지비가 들며, 이장은 이 유지비를 최소로 유지하고 싶다. 또한, 마을이 너무 커서 2개의 마을로 분할하려 하는데 분할된 각 마을의 모든 집은 길이 연결되어있어야 한다. 분리된 마을은 이어질 수 없으며 분할된 각 마을에서 집 사이에 연결된 길의 유지비의 합이 최소이고 싶다. 이것을 구하는 프로그램을 작성하시오.

문제 풀이 포인트

문제를 요약하자면, MST(최소 신장 트리, Minimun Spanning Tree)를 구하는 문제이다. 마을 전체의 MST를 구한 이후에 연결된 간선들중 하나를 끊으면 2개의 마을에서

  • 2개의 마을은 연결되지 않으며,
  • 임의의 두 집 사이의 경로는 항상 존재하고,
  • 2개의 마을의 길의 유지비의 합은 항상 최소로 유지된다.

문제의 입력은 간선의 정보가 주어지므로 크루스칼(Kruskal) 알고리즘을 사용하여 MST를 구성하면 된다.

문제 코드[JAVA]

코드 펼치기 

import java.util.*;
import java.io.*;
public class Main {
  static int N, M;
  static int parents[];
  static int ranks[];
  static Edge[] edgeList;
  static class Edge implements Comparable<Edge>{
    int from, to, weight;

    public Edge(int from, int to, int weight) {
      super();
      this.from = from;
      this.to = to;
      this.weight = weight;
    }

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

  }
  static void make() {
    for(int i = 1; i < parents.length; i++) {
      parents[i] = i;
    }
  }
  static int find(int a) {
    if(parents[a] == a) return a;
    return parents[a] = find(parents[a]);
  }
  static boolean union(int a, int b) {
    int aRoot = find(a);
    int bRoot = find(b);
    if(aRoot == bRoot) return false;

    if(ranks[bRoot] > ranks[aRoot]) parents[aRoot] = bRoot;
    else {
      parents[bRoot] = aRoot;
      if(ranks[bRoot] == ranks[aRoot]) ranks[aRoot]++;
    }
    return true;
  }
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    parents = new int[N+1];
    ranks = new int[N+1];
    make();
    edgeList = new Edge[M];
    for(int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      edgeList[i] = new Edge(Integer.parseInt(st.nextToken()), 
      Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }
    Arrays.sort(edgeList);
    int result = 0;
    Stack<Edge> stack = new Stack<>();

    // 크루스칼 알고리즘과 동일하게 적용
    // 단 최소신장 트리에서 2개로 쪼개야 하므로 최소신장트리를 구성하는 간선들을 stack에 담음
    for(Edge edge : edgeList) {
      if(union(edge.from, edge.to)) {
        result += edge.weight;
        stack.push(edge);
        if(stack.size() == N-1) break;
      }
    }
    int min = Integer.MAX_VALUE;
    // 각 간선들을 결과에 하나씩 빼보며 최소값을 찾음
    while(!stack.isEmpty()) {
      min = Math.min(result - stack.pop().weight, min);
    }
    System.out.println(min);
  }
}

Related posts