[백준 11085] 군사 이동 (C++)

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

11085번: 군사 이동

1. 주의할 점

- 가중치가 큰 간선들부터 연결을 한다

- 크루스칼 알고리즘을 사용한다. 단, 종료조건이 다르다

 

2. 구현

- 입력 받는 간선에 대한 정보를 우선순위큐에 저장하며, 가중치의 내림차순으로 정렬한다

- 우선순위큐에서 간선에 대한 정보를 1개씩 빼면서 만약 2개의 도시가 이어져 있지 않다면 연결하고, Result에 해당 간선의 가중치를 부여한다.

- 만약 시작점과 도착점의 부모가 같다면 우선순위큐에서 빼는것을 종료한다

- Find_par(x) 함수를 통해 X의 부모를 재설정 및 반환한다

- Make_union(a,b) 함수를 통해 A와 B의 부모를 통일시킨다

 

#define MAX 987654321
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	int s, e, val;
};
struct cmp {
	bool operator()(info &a,info &b){
		return a.val < b.val;
	}
};
info tmp;
int node, edge, s, e, val,start,destination;
int par[1001];

int find_par(int x) {
	if (par[x] == x) return x;
	return par[x] = find_par(par[x]);
}

void make_union(int a, int b) {
	a = find_par(a);
	b = find_par(b);
	if (a < b) par[b] = a;
	else if (a > b) par[a] = b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge >> start >> destination;
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.val = val;
		tmp.e = e;
		tmp.s = s;
		pq.push(tmp);
	}
	for (int i = 0; i < node; i++)
		par[i] = i;
	int result;
	while (!pq.empty()) {
		int cs = pq.top().s;
		int ce = pq.top().e;
		int cv = pq.top().val;
		pq.pop();
		if (find_par(start) == find_par(destination)) break;
		int ps = find_par(cs);
		int pe = find_par(ce);
		if (ps == pe) continue;
		make_union(cs, ce);
		result = cv;
	}
	cout << result;
	system("pause");
	return 0;
}