[ 백준 ] 1647번 - 도시 분할 계획 (c++)

그래프 문제로 어려운 난이도는 아니지만 좋은 문제 같아서 정리해보려한다.

풀이를 생각하는 과정이 마음에 들었다.

 

<문제>

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

1647번: 도시 분할 계획

 

<풀이>

마을 안의 도시끼리 한 길로만 연결되고 나머지 길은 없앨 수 있다는 점에서 최소 스패닝 트리를 생각했다.

크루스칼 알고리즘을 사용하여 풀 수 있다. 유지비를 최소로 하기 위해서 정렬 후 유지비가 작은 길부터 크루스칼 알고리즘을 사용하면 된다. 그런데, 두 마을로 나눈다는 것 때문에 약간의 응용이 필요하다.

두 마을이 연결되는 길 하나만 없애면 즉, 마지막으로 연결되는 제일 큰 유지비 값을 빼면 최소 유지비를 구할 수 있다. 

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

int parent[100001];

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

bool sameParent(int x, int y){
  return getParent(x) == getParent(y);
}

void Union(int x, int y){
  x = getParent(x);
  y = getParent(y);
  if(x<y) parent[y] = x;
  else if(x>y) parent[x] = y;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  int n,m,sum=0;
  cin>>n>>m;
  vector<pair<int, pair<int,int>>> node;
  vector<int> result;
  
  for(int i=1; i<=n; i++) parent[i] = i;
  
  for(int i=0; i<m; i++){
    int a,b,c;
    cin>>a>>b>>c;
    node.push_back({c, {a,b}});
  }
  sort(node.begin(), node.end());
  
  for(int i=0; i<node.size(); i++){
    int a = node[i].second.first;
    int b = node[i].second.second;
    int c = node[i].first;
    
    if(!sameParent(a, b)){
      Union(a,b);
      result.push_back(c);
    }
  }
  
  for(int i=0; i<result.size()-1; i++)
    sum += result[i];
  cout<<sum;
}