정복자 [BOJ14950]

문제

1번 도시에서 시작해서 모든 도시를 정복하는데 걸리는 최소 비용을 구하시오.

어떤 도시를 정복하려면 이미 정복된 도시에서 연결된 가중치 만큼의 비용이 든다.

한도시가 점령될 때 마다 다른 모든 도시의 가중치가 1씩 올라간다.

한번 정복한 도시는 다시는 정복하지 않는다.

1번도시에서의 출발조건을 무시해도 괜찮을까

출발노드가 고정된 채 문제를 생각해보면 너무 어렵다. 1번 다음에 당장 어떤 노드를 선택해야 할지 모르기 때문이다. 그래서 모든 도시를 연결하는 최소 가중치를 찾고, 1번부터 시작했다고 하면 된다.

최소스패닝트리문제다!!

이전 문제에서 최소스패닝트리에 대해서 배우고 왔더니, 이 문제는 최소스패닝트리로 가볍게 풀릴 것 같았다.

모든 노드를 연결해야하고, 재방문이 없다는 점에서 사이클이 생기지 않으므로 최소 스패닝 트리와 문제는 동일하다. 다른점이라면 정복될 때마다 모든 도로의 가중치가 t가 올라간다는 점이다.

가중치1 추가를 무시해도 괜찮을까

어차피 트리니까 간선의 개수는 n-1개로 고정되어있다. 그렇기에 이 조건이 존재함으로써 증가하는 가중치는 t x(1+2+…+n-1)로 미리 구할 수 있다.

모든 도로는 동일하게 t만큼 증가한다. 그렇기에 도로의 가중치 우선순위는 변동되지 않는다. 이 우선순위가 변하지 않는다는 것은 크루스칼 알고리즘을 동일하게 적용할 수 있다는 의미이다.

code

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

// 간선을 표현하는 구조체
struct Edge {
    int src, dest, weight;
};

// 유니온-파인드 알고리즘을 위한 함수들
int find(vector<int>& parent, int i) {
    if (parent[i] == i) return i;
    return find(parent, parent[i]);
}

void Union(vector<int>& parent, int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    if(xset < yset) parent[xset] = yset;
    if(xset > yset) parent[yset] = xset;
}

// 크루스칼 알고리즘
int kruskalMST(vector<Edge>& edges, int n) {
    int mst_weight = 0;

    // 간선들을 가중치 기준으로 정렬
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        return a.weight < b.weight;
    });

    vector<int> parent(n + 1);
    for (int i = 1; i <= n; ++i) parent[i] = i;

    for (Edge &edge : edges) {
        int x = find(parent, edge.src);
        int y = find(parent, edge.dest);

        if (x != y) {
            mst_weight += edge.weight;
            Union(parent, x, y);
        }
    }

    return mst_weight;
}

int main() {
		ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, t;
    cin >> n >> m >> t;

    vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }

    cout << kruskalMST(edges, n) + t * (n-1) * (n-2) / 2 << endl;

    return 0;
}