[백준 1647] 도시 분할 계획 (C++)

문제 링크: https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

1. 주의할 점

- MST(최소 신장 트리)를 해결하기 위해 프림 알고리즘과 크루스칼 알고리즘이 존재하는데 둘중 1개라도 알고 있어야 한다

 

2. 구현

- 프림 알고리즘을 적용해 문제를 해결한다

- 우선 MST를 구축하고, 1개의 마을 -> 2개의 마을로 나눈다고 했으므로 MST를 이루는 간선중 가장 값이 큰 간선을 제거하면 결과를 유추할 수 있다

- V 벡터를 통해 해당 Node에 연결된 간선들의 정보를 담는다

- 아무 Node 한개를 잡고 Queue에 넣고 시작한다(코드에선 1번 Node를 추가)

- Queue에서 빼면서 Visit값을 True로 바꾸고 해당 Node에 연결된 모든 간선 중에서 아직 방문하지 않은 Node를 포함하는 간선을 우선순위 큐에 넣는다

- 우선순위 큐에서 1개씩 빼면서 이미 방문한 Node면 Skip, 방문하지 않은 Node면 큐에 넣고 Result에 간선의 가중치를 추가한다. 그리고 Maxi와 비교하면서 Maxi는 간선중 가장 큰 값어치를 가지고 있도록 유지한다

- 프림 알고리즘이 끝난 후, Result - Maxi를 통해 결과를 출력한다

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
vector<info> v[100001];
bool visit[100001] = { false, };

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, edge, s, e, val, maxi = 0;
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.val = val;
		tmp.idx = e;
		v[s].push_back(tmp);
		tmp.idx = s;
		v[e].push_back(tmp);
	}
	queue<int> q;
	priority_queue<info, vector<info>, cmp> pq;
	q.push(1);
	long long result = 0;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		visit[cidx] = true;
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i].idx;
			int nv = v[cidx][i].val;
			if (!visit[next]) {
				tmp.idx = next;
				tmp.val = nv;
				pq.push(tmp);
			}
		}
		while (!pq.empty()) {
			int next = pq.top().idx;
			int nv = pq.top().val;
			pq.pop();
			if (visit[next]) continue;
			visit[next] = true;
			result += nv;
			maxi = max(maxi, nv);
			q.push(next);
			break;
		}
	}
	cout << result - maxi;
	system("pause");
	return 0;
}