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

embeddedjune·2020년 10월 1일
0

알고리즘::동빈나책

목록 보기
21/23

문제

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

문제접근

  • 전형적인 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

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글