백준 1647번: 도시 분할 계획 (C++)

문제링크

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

풀이방법

해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자.

https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28

우선 마을 하나하나를 그래프의 노드라고 생각한다. 그 상태로 최소 신장 트리를 만든다. 그럼 모든 마을이 연결되어있고 가중치의 합이 최소인 상태가 된다. 즉, 길의 유지비가 최소가 된 상태다. 이 상태에서 마을을 분할하면 되는데 정말 쉽게 생각하면 특정 노드와 노드 사이의 유지비가 가장 비싼 구간을 하나 끊어버리면 길의 유지비가 최소가 되면서 마을을 분리 시킬 수 있다.

코드

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

priority_queue< tuple<int, int, int>,
                vector<tuple<int, int, int>>,
                greater<tuple<int, int, int>> > pq;

vector< pair<int, int> > adj[100002];
bool vis[100002];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, m;
  cin >> n >> m;

  int a, b, c;
  while(m--) {
    cin >> a >> b >> c;
    adj[a].push_back({c, b});
    adj[b].push_back({c, a});
  }

  vis[1] = 1;
  for(auto nxt : adj[1])
    pq.push({nxt.first, 1, nxt.second});
  
  int cnt = 0, ans = 0, mc = 0;
  while(cnt < n - 1) {
    tie(c, a, b) = pq.top(); pq.pop();
    if(vis[b]) continue;

    vis[b] = 1;
    ans += c;
    mc = max(mc, c);
    cnt++;

    for(auto nxt : adj[b])
      if(!vis[nxt.second])
        pq.push({nxt.first, b, nxt.second});
  }
  cout << ans - mc;
}

/*
선택된 경로들의 유지비 중 가장 큰 값을 mc변수에 갱신
MST 구축 후 총 유지비에서 mc 값을 뺌
*/