[백준] 1647번: 도시 분할 계획 (C++)

문제 링크

1647번: 도시 분할 계획

---

예전에 분리집합(union-find)을 배우고 나서, 분리집합을 응용한 알고리즘인 최소 스패닝 트리를 공부해야지~ 하고 생각했다가 미루고 미뤄서(...) 최근에 공부하게 됐습니다.

기본적인 최소 스패닝 트리 문제를 한번 풀어보겠습니다.

풀이

최소 스패닝 트리(분리 집합) 알고리즘 으로 푸는 문제입니다.

문제가 복잡해 보이지만, 간단한 해결방법이 존재합니다. 문제에서는 다음과 같은 조건을 제시했습니다.

1. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있습니다.
2. 임의의 두 집 사이에 경로를 항상 존재하게 하면서 길을 없애야 합니다.
3. 길들을 없앤 뒤 나머지 길들의 유지비의 합을 최소로 해야 합니다.

두 조건을 간단하게 말하자면, 크루스칼로 각 마을을 최소 유지비로 연결하되, 마을을 2개로 분리시켜라 라는 말이 됩니다.

여기서 마을을 2개로 분리시키라는 말이 어려울 수 있지만, 최소 스패닝 트리의 원리를 다시 생각해보면 쉽습니다.

최소 스패닝 트리는 가중치가 최소인 간선 또는 점만 골라, 모든 점을 연결하는 트리입니다.

이 트리에서 모든 점을 연결한다고 한다(=트리가 1개)는 사실을 이용해서, 하나의 간선을 자르면 트리가 자동으로 2개로 분리가 됩니다.

또 문제에서 최소 유지비로 연결하라고 했기 때문에, 트리를 분리시킬 때 최대값의 간선을 분리시키면 자동으로 2개의 트리로 분리가 되면서 최소의 유지비로 연결될 것입니다!

즉, 다음과 같은 흐름으로 풀이를 하면 됩니다.

1. 최소 유지비로 간선을 연결하기 위해, 주어진 길을 오름차순으로 정렬해줍니다.
2. 오름차순으로 정렬된 길을 분리 집합으로 찾으면서 연결(`uniParent`)시킵니다.
3. 연결된 간선의 유지비를 모두 더해주되, 맨 마지막(최대값) 간선의 유지비만 빼줍니다.

풀이코드

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

vector<tuple<int,int,int>> graph;
int parent[100001];

int getParent(int x) {
  if (parent[x] == x) return x;
  return parent[x] = getParent(parent[x]);
}

void uniParent(int a, int b) {
  a = getParent(a);
  b = getParent(b);
  if (a != b) parent[b] = a;
}

void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) parent[i] = i;
  while (m--) {
    int a, b, c;
    cin >> a >> b >> c;
    graph.push_back({c,a,b});
  }
  sort(graph.begin(), graph.end());

  int sum = 0, cur = 0;
  for (auto [c, a, b] : graph) {
    if (getParent(a) != getParent(b)) {
      sum += (cur = c);
      uniParent(a, b);
    }
  }
  sum -= cur;
  cout << sum; 
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

• 31번줄의 `cur`이 유지비입니다.

배운점

• 분리집합을 다시 복습할 수 있었습니다.
• 최소 스패닝 트리(크루스칼)의 개념에 대해 다시 복습할 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!