알고리즘 :: 이것이 코딩 테스트다 :: 그래프 이론 문제 :: Q43 :: 어두운 길

문제

특정한 도로의 가로등을 하루동안 켜기 위한 비용은 해당 도로의 길이와 동일하다. 정부에서는 일부 가로등을 비활성화해서 절약할 수 있는 최대 금액을 구하고자 한다.

문제접근

• 전형적인 MST (최소 신장 트리) 문제다.
• 입력받은 간선을 cost에 대해 오름차순으로 정렬한 뒤 가장 적은 cost의 간선부터 그래프에 추가하면서 사이클이 생기는지 생기지 않는지 여부를 확인한다.
• 서로소 집합은 여기서 사이클 존재 여부를 확인하기 위해 사용된다!
• 임의의 간선에 포함된 두 정점을 연결하려고 할 떄 두 정점이 같은 root를 가지고 있다면 사이클이 발생한것이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

static int N, M, rootInfo[200001];
static vector<pair<int, pair<int, int>>> road;

int findOperation(int x) {
    if (rootInfo[x] != x) return findOperation(rootInfo[x]);
    return rootInfo[x];
}
void unionOperation (int lhs, int rhs) {
    lhs = findOperation(lhs), rhs = findOperation(rhs);
    (lhs < rhs) ? (rootInfo[rhs] = lhs) : (rootInfo[lhs] = rhs);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M;
    // [과정1]: rootInfo 배열을 초기화: N개의 그룹으로 나눈다.
    for (int i = 1; i <= N; ++i) rootInfo[i] = i;
    // [과정2]: 도로를 입력받고 최대 cost를 계산한다.
    int maxCost = 0;
    for (int i = 0; i < M; ++i) {
        int s, e, w;    cin >> s >> e >> w;
        road.push_back({w, {s, e}});
        maxCost += w;
    }
    // [과정3]: 크루스칼 알고리즘을 위해 cost에 대해 오름차순 정렬한다.
    sort(begin(road), end(road));
    // [과정4]: 적은 cost 도로부터 mst에 포함시킨다.
    for (const auto& itr : road) {
        if (findOperation(itr.second.first) != findOperation(itr.second.second)) {
            unionOperation(itr.second.first, itr.second.second);
            maxCost -= itr.first;	// 절약한 cost를 구하기 위해 써야하는 cost를 감산한다.
        }
    }
    cout << maxCost << '\n';
}

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11

51

결과