[백준 10423 C++][G2] 전기가 부족해

⭐️ 난이도

 

Gold 2

---

⭐️ 문제

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

10423번: 전기가 부족해

 

---

⭐️ Idea flow

 

MST를 통해 풀 수 있는 문제였다.

 

그런데 왜 MST로 푸는 문제일까?

발전소(시작 지점)이 한 군데가 아니기 때문에 다른 알고리즘을 사용해야하나 고민했다.

하지만 목적지가 따로 없고, 모든 노드(도시)를 연결해야 하는 문제이므로 MST 문제라고 판단했다.

 

왜 prim 알고리즘을 사용해야 할까?

예시를 통해 문제를 시뮬레이션하면서 가중치가 적은 간선을 선택하는 동시에 발전소가 있는 도시가 서로 연결되지 않게 연결을 했다.

그랬더니 원하는 결과가 나왔다.

하지만 크루스칼 알고리즘을 사용하면 간선을 연결하면서 어떤 발전소와 연결되어 있는지 확인하기 힘들다는 단점이 있다.

반면 프림 알고리즘을 사용하면 현재까지 선택된 정점을 기준으로 주변 간선들을 확인하기 때문에 어떤 발전소와 연결되어 있는지 확인하기가 더 용이하다.

 

연결된 도시에서 발전소가 설치된 도시는 하나만 있어야 한다!

정점을 방문하면서 해당 정점(도시)가 어떤 발전소와 연결되어 있는지 확인을 해야 하나?라는 의구심이 들었다.

정점을 선택하는 과정을 겪기 전에 발전소가 있는 도시의 주변 간선을 모두 우선순위 큐에 push하는 과정을 거친다.

이후 정점을 선택하는데, 이 때 만약 해당 정점을 방문했다는 것은 곧 발전소와 연결되어 있다는 뜻이고,

MST는 사이클이 없는 그래프. 즉 Tree이기 때문에 어떤 발전소와 연결되어 있는지 따로 처리는 필요없다고 판단했다.

 

 

[전체 알고리즘]

1. input을 받으면서 정점을 잇는 간선의 정보를 변수 graph에, 발전소가 있는 도시의 정보는 변수 generator에 담는다.

2. generator를 반복문으로 돌면서 해당 도시를 방문처리하고, 해당 도시와 연결되어 있는 간선들을 우선순위 큐에 삽입한다.

3. 프림 알고리즘을 실행한다. 프림 알고리즘을 통해서 최소 비용인 간선(케이블)들을 선택할 것이다.

 

 

---

⭐️ Code

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

#define INF 987654321;
using namespace std;

// 10423 - 전기가 부족해
int n, m, k; // 도시의 수, 케이블의 수, 발전 도시의 수
vector<vector<pair<int, int>>> graph;
vector<int> isVisited; // 정점 방문 여부 저장
vector<int> generator; // 발전소가 설치된 도시의 정보 저장

void input(){
    cin >> n >> m >> k;

    graph.assign(n + 1, vector<pair<int, int>>{});
    isVisited.assign(n + 1, false);
    generator.assign(k, 0);

    // 발전소가 설치된 도시의 번호
    for(int i = 0; i < k; i++){
        cin >> generator[i];
    }

    // 케이블 연결
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }
}

void setGenerator(priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>>& pq){
    // 발전소가 설치되어 있는 도시와 연결되어있는 간선의 정보를 넣는다.
    for(int i = 0; i < k; i++){
        isVisited[generator[i]] = true;
        for(int j = 0; j < graph[generator[i]].size(); j++){
            // 간선의 비용, 연결된 도시의 번호
            pq.push({graph[generator[i]][j].second, graph[generator[i]][j].first});
        }
    }
}

void prim(){
    int sum = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    setGenerator(pq);

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

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

            for(int i = 0; i < graph[cur].size(); i++){
                int next = graph[cur][i].first;
                int n_cost = graph[cur][i].second;
                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;
}