[백준][C++] 21924 도시 건설

21924. 도시 건설
문제 풀이

21924번: 도시 건설

 

전체 간선의 비용 - MST의 비용을 구하는 문제!

쉬워 보이는 문제였다만, 다만... 모든 노드가 연결되어있지 않으면 -1을 출력해야 하는 조건 때문에 조금 고민을 했다.

알고리즘

간선의 수가 꽤 많았기 때문에, 프림 알고리즘을 사용하였다.

모든 노드가 연결되지 않을 때를 처리해주기 위해, 그때 발생하는 일을 확인해보았다.

이 줄에서 top이 없어서 오류가 났다.

즉, V-1개의 간선을 구하기 전에 우선순위 큐가 빈다는 것이다!

 

그래서 우선순위 큐 비어있는지 체크해주고, 마지막에 V-1개의 간선이 선택되지 않았다면 -1을 출력하기로 했다.

 

코드

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

vector<pii> nodes[100001];
bool visited[100001];

int main()
{
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    int vCnt, lCnt;
    int temp = 0;
    long long int total = 0, mstSum = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pQueue;
    cin >> vCnt >> lCnt;

    for (int i = 0; i < lCnt; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        nodes[a].push_back({ w,b });
        nodes[b].push_back({ w,a });

        // 모든 간선의 가중치 더함
        total += w;
    }

    pQueue.push({ 0,1 });

    // 프림 알고리즘
    while (vCnt && !pQueue.empty())
    {
        int cost = pQueue.top().first;
        int node = pQueue.top().second;
        pQueue.pop();

        if (!visited[node])
        {
            mstSum += cost;
            vCnt--;
            visited[node] = true;

            for (int i = 0; i < nodes[node].size(); i++)
            {
                if (!visited[nodes[node][i].second])
                {
                    pQueue.push({ nodes[node][i].first, nodes[node][i].second });
                }
            }
        }
    }

    // 모든 노드를 연결하지 못했다면
    if (vCnt > 0)
        cout << -1;
    else
        cout << total - mstSum;
}

모든 노드가 연결되지 않은 상태를 체크할 수 있어서 재미있었다!