[백준 14950 C++][G3] 정복자

⭐️ 난이도

 

Gold 3

---

⭐️ 문제

https://www.acmicpc.net/problem/14950

14950번: 정복자

 

 

---

⭐️ Idea flow

 

문제를 읽으면서 이 문제에 MST의 일종인 Prim 알고리즘을 사용해야겠다고 생각했다.

그럼 먼저 이 문제가 왜 MST 관련 문제일까?

    → 모든 도시를 최소 비용으로 연결해야하기 때문이다. shortest path problem와는 달리, 특정 목적지가 정해져있지 않다.

그럼 두 번째로 왜 Prim 알고리즘을 사용해야 할까?

    → Kruskal(크루스칼) 알고리즘은 간선을 정렬한 후, 간선을 선택하는 방식이다.

        하지만 이 문제의 경우 특정 노드를 방문하기 위해서는, 해당 노드와 연결되어 있는 다른 노드를 방문해야 한다.

        이러한 방문 방법은 정점을 중점으로 하는 Prim 알고리즘이 적절하다.

 

다음으로 해결해야 하는 포인트는 "한 번 도시가 정복되면, 모든 도로의 비용이 t만큼 증가"하는 것이다.

우선 int형 변수 time을 선언한다. 이는 도시를 정복한 횟수를 저장하는 변수이다.

Prim 알고리즘을 진행하다가 정점을 하나 선택하게 되면

1) 결과 값(sum)에 cost(현재까지의 비용) + time * t(정복 횟수 * 증가 비용)을 더해준다.

   이렇게 하면 

2) 도시를 정복했다는 의미이므로 time++을 해준다.

 

prim 알고리즘이 모두 끝나면 sum이 바로 모든 도시를 정복하는데 사용되는 최소 비용이다.

 

---

⭐️ Code

 

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_set>

#define INF 987654321;
using namespace std;

// 14950 - 정복자
int n, m, t; // 도시의 개수, 도로의 개수, 증가하는 도로의 비용
int sum = 0, time = 0;
vector<int> isVisited;
vector<vector<pair<int, int>>> graph; // first: next, second: cost

void input(){
    cin >> n >> m >> t;
    isVisited.assign(n + 1, false);
    graph.assign(n + 1, vector<pair<int, int>>{});

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].emplace_back(b, c);
        graph[b].emplace_back(a, c);
    }
}

void prim(){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    isVisited[1] = true;
    for(int i = 0; i < graph[1].size(); i++){
        pq.push({graph[1][i].second, graph[1][i].first});
    }

    while(!pq.empty()){
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if(!isVisited[cur]){
            isVisited[cur] = true;
            sum += cost + t * time;
            time++;

            for(int i = 0; i < graph[cur].size(); i++){
                int n_cost = graph[cur][i].second;
                int next = graph[cur][i].first;
                if(!isVisited[next])    pq.push({n_cost, next});
            }
        }
    }
    cout << sum;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    prim();

    return 0;
}