[C++] 어두운 길

1. 문제

한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N - 1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다.
정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요.

2. 입력 조건

• 첫째 줄에 집의 수 N(1 ≤ N ≤ 200,000)과 도로의 수 M(1 ≤ M ≤ 200,000)이 주어집니다.
• 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X, Y, Z가 주어지며, 공백으로 구분합니다. (0 ≤ X, Y, Z ≤ N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미입니다. 단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이의 합은 2^31보다 작습니다.

3. 출력 조건

• 첫째 줄에 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력합니다.

4. 풀이

• 크루스칼 알고리즘 문제이다.
• 금액을 최대한 절약하려면 연결된 도로 비용의 합이 최소가 되어야 한다.
• 각 도로의 정보를 입력 받고 비용 순으로 정렬한다.
• 비용이 적은 순서대로 도로를 확인하며 사이클이 발생(=부모가 같음)하는지 확인한다.
• 도로 비용의 총합에서 새롭게 만든 절약된 도로 비용의 총합을 빼서 출력한다.

5. 처음 코드와 달라진 점

• null

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int parent[2000001];
vector<pair<int, pair<int, int> > > roads;

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

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

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin>>n>>m;

  for (int i = 0; i < n; i++) {
    parent[i] = i;
  }
  
  int totalCost = 0;
  for (int i = 0; i < m; i++) {
    int a, b, cost;
    cin>>a>>b>>cost;

    totalCost += cost;
    roads.push_back(make_pair(cost, make_pair(a, b)));
  }

  sort(roads.begin(), roads.end());

  int savedCost = 0;
  for (int i = 0; i < m; i++) {
    int cost = roads[i].first;
    int a = roads[i].second.first;
    int b = roads[i].second.second;

    if(findParent(a) != findParent(b)) {
      savedCost += cost;
      unionParent(a, b);
    }
  }
  
  cout<<totalCost - savedCost;
}