[백준 / BOJ] C++ 1647 도시 분할 계획

1647번: 도시 분할 계획

 

문제

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

1647번: 도시 분할 계획

 

 

풀이

가장 짧은 도로들만 가지고 모든 집이 연결되어 있어야 하므로 집을 정점, 도로를 간선이라고 생각하고 최소 스패닝 트리(MST)를 구하면 된다. 단, 도시를 두 개의 마을로 나눠야 하고 각 마을에는 집이 최소 하나는 있어야 하므로 MST의 간선 중 길이가 가장 긴 간선을 제거해 주면 된다.

 

 

코드

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

int V, E, len = 0;
vector<pii> graph[100001];

int prim() {
  priority_queue<pii> pq;
  vector<int> visited(V + 1, 0);
  visited[1] = 1;
  for (pii edge : graph[1])
    pq.push(edge);
  int cost = 0;
  while (!pq.empty()) {
    int weight = -pq.top().first;
    int node = pq.top().second;
    pq.pop();
    if (!visited[node]) {
      visited[node] = 1;
      len = max(len, weight); // 가장 긴 간선 갱신
      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;
  while (E--) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({-c, b});
    graph[b].push_back({-c, a});
  }
  // MST의 가중치 - MST의 간선 중 가장 가중치가 큰 간선
  cout << prim() - len;
  return 0;
}