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

10423번: 전기가 부족해

 

문제

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

10423번: 전기가 부족해

 

 

풀이

이렇게 하면 될까? 했는데 돼서 푼 다음에 이해를 했다. 여러 발전소에서 전력 공급이 가능하기 때문에 프림 알고리즘을 사용하는 최소 스패닝 트리(MST)에서 우선순위 큐에 발전소와 연결된 모든 간선을 넣어줬다. 그리고 MST의 가중치를 구하면 끝!

 

이를 개념적으로 이해를 해보자면, 결국 최소 스패닝 트리를 만들기 위해서는 최소 비용의 간선을 통해 계속해서 확장해 나간다. 따라서 미리 발전소를 MST에 포함시킨 다음 최소 비용의 간선으로 확장해 나간다고 이해를 했다. 그런 다음 기여에서 다른 사람들의 풀이를 봤는데 발전소들을 하나로 생각하고 시작한 것이다. 어차피 그래프이고 MST에 반드시 포함되어야 하기 때문에 이렇게 생각하니 이해가 훨씬 쉽게 됐다. (사실 방식 자체는 같다!)

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

int V, E, K;
vector<pii> graph[100001];
priority_queue<pii> pq;
vector<int> visited(100001, 0);

// 프림 알고리즘을 사용한 MST
int prim() {
  int cost = 0;
  while (!pq.empty()) {
    int weight = -pq.top().first;
    int node = pq.top().second;
    pq.pop();
    if (!visited[node]) {
      visited[node] = 1;
      cost += weight;
      for (pii next : graph[node])
        if (!visited[next.second])
          pq.push(next);
    }
  }
  return cost;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> V >> E >> K;
  // 발전소 위치 기록
  vector<int> p(K);
  for (int i = 0; i < K; i++)
    cin >> p[i];
  // 간선 입력
  while (E--) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({-c, b});
    graph[b].push_back({-c, a});
  }
  // 발전소와 연결된 간선 모두 우선순위 큐에 추가
  for (int i : p) {
    visited[i] = 1;
    for (pii edge : graph[i])
      pq.push(edge);
  }
  // MST
  cout << prim();
  return 0;
}