[백준/C++] 6497번. 전력난

[백준/C++] 6497번. 전력난

1. 문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

2. 입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

3. 출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

4. 풀이

• 최소 신장 트리 문제
• m, n을 입력받는 while-loop를 만들고 m과 n이 모두 0일 때까지 반복한다.
• parernt 배열을 자기 자신으로 초기화 해준다.
• m개의 도로 정보를 받아 온다.
  도로 정보를 받아오면서 비용의 총합을 미리 구해둔다
• 도로 정보를 비용 오름차순으로 정렬한다.
  비용이 적은 도로를 우선 건설하기 위함
• 도로 정보를 하나씩 가져 오면서 사이클이 생기지 않는(=부모가 같지 않은) 도로를 건설한다.
  건설한 도로 비용을 더해서 구한다.
• 도로를 건설했다면 두 마을을 합집합한다.
• 모든 도로를 건설하는데 드는 비용에서 새로 건설한 도로의 비용을
  빼면 절약한 비용이 나온다.

5. 처음 코드와 달라진 점

• parent 배열을 초기화 해주지 않아서 수정했다.

6. 코드

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

using namespace std;

int parent[200000];


int findParent(int x) {
  if (x == parent[x]) return x;
  else return parent[x] = 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);

  while (true) {
    vector<pair<int, pair<int, int> > > v;
    int m, n;
    cin >> m >> n;

    if (m == 0 && n == 0) break;

    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
    
    
    int totalCost = 0;
    for (int i = 0; i < n; i++) {
      int a, b, cost;
      cin >> a >> b >> cost;
      
      totalCost += cost;
      v.push_back(make_pair(cost, make_pair(a, b)));
    }
    sort(v.begin(), v.end());

    int newCost = 0;
    for (int i = 0; i < v.size(); i++) {
      int a = v[i].second.first;
      int b = v[i].second.second;
      int cost = v[i].first;

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