백준 14950 정복자

문제 설명

• N개의 도시와 N개의 도로가 있고, 각 도시는 최소 하나 이상의 도로로 연결되어 있다.
• 1번 도시를 점거하고 있는데 모든 도시를 점거하는 것이 목표다
• 한 도시를 점거하려면 그 도시로 일정 비용을 지불하고 도로를 사용하여 이동하면 정복할 수 있다.
• 이때 한 도시가 점거당하면 다른 도시들은 모든 도로 사용 비용을 t만큼 증가시킨다.
• 모든 도시를 점거하는 최소 비용을 구해라

문제 링크

접근 방법

• 다익스트라, 폴로이드 알고리즘을 떠올려도 문제 해결 방법이 떠오르지 않아서 분류를 보니 처음보는 최소 스패닝 트리라는 알고리즘이었다.
• 나는 최소 스패닝 트리 구현 알고리즘 중에 크루스칼 알고리즘을 사용했는데, 이는 유니온 파인드와 그리디 알고리즘을 섞은 느낌이었다.
• 모든 도로를 비용 순으로 정렬하고 가장 적은 비용이 든 도로부터 유니온 파인드를 진행하면서 비용을 구한다
• 지금까지 점거한 도시의 수를 세면서 점거 비용 = 도로 비용 + t * (지금까지 점거한 도시의 수) 라는 식을 이용해서 비용을 계산했다.

배운점

• 전체 노드를 방문해야하는 경우의 알고리즘은 최소 스패닝 트리를 떠올려야 한다.
• 사실 이미 알고 있는 알고리즘을 조합한 알고리즘이라 해당 알고리즘을 몰랐어도 구현이 가능했어야 한다고 생각한다.(반성중)
• touple과 tie를 함께 사용하면 코드의 길이를 줄일 수 있는 아주 강력한 방법이 된다.

구현 코드

#include <queue>
#include <iostream>
#include <algorithm>
#include <utility>
#include <tuple>

using namespace std;

int    group[10001];
tuple<int, int, int>    line[30001];

int find(int a)
{
    if (group[a] < 0)
        return (a);
    group[a] = find(group[a]);
    return (group[a]);
}

bool uni(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b)
        return (false);
    group[b] = a;
    return (true);
}


int main()
{
    int N, M, t, A, B, C;
    int ret = 0;
    int count = 0;

    cin>>N>>M>>t;
    fill(group, group + 10001, -1);
    for (int i = 0; i < M; i++)
    {
        cin>>A>>B>>C;
        line[i] = tie(C, A, B);
    }
    sort(line, line + M);
    for (int i = 0; i < M; i++)
    {
        tie(C, A, B) = line[i];
        if (uni(A, B))
        {
            ret += C + count * t;
            count++;
        }
    }
    cout<<ret<<endl;
}