C++ / 백준 / 13905 / 세부

문제

 

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

13905번: 세부

문제풀이

 

크루스칼 알고리즘으로 풀었다.

 

구조체를 선언하여 섬 1, 섬 2, 무게 제한을 변수로 둔다.

부모를 찾는 find, 두 노드 같은 사이클로 만드는 Union, 두 노드가 같은 사이클인지를 판별하는 isUnion 함수를 구현한다.

 

모든 입력을 다 받았으면, 정렬을 해야 한다.

가장 작은 길이로 시작점과 도착점을 연결하는 것이 아닌, 최대 개수를 구하는 것이므로 무게 제한을 내림차순으로 정렬한다.

 

	for (int idx = 0; idx < M; ++idx) {
		island1 = bridges[idx].island1;
		island2 = bridges[idx].island2;
		if (isUnion(island1, island2) == true) continue;
		else {
			Union(island1, island2);
			if (find(start) == find(end)) {
				cout << bridges[idx].limit;
				return 0;
			}
		}
	}
	cout << "0";

그다음은 입력받은 다리 개수만큼 반복문을 반복한다.

먼저 저장된 구조체에서 두 섬과, 두 섬을 잇는 다리를 구한다.

isUnion을 통해 두 섬이 같은 사이클에 있는지를 판별한다.

 

만약 이미 사이클이 형성된 두 섬이라면 continue를 통해 넘긴다.

그렇지 않다면 Union함수를 통해 사이클을 형성해 준다.

 

만약 시작 섬과 도착 섬이 같은 사이클 안에 있다면 (두 섬의 find 함수의 return 값이 같다면) 현재 인덱스의 무게 제한 값을 출력하고 종료하면 된다.

 

만약 모든 다리를 탐색했는데도 연결이 안 되었다면 연결할 수 없으므로 0을 출력한다.

 

코드

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

vector<int>parent;

struct Bridge {
	int island1;
	int island2;
	int limit;
};

bool cmp(Bridge& b1, Bridge& b2) {
	return b1.limit > b2.limit;
}

int find(int node) {
	if (parent[node] == node) return node;
	return parent[node] = find(parent[node]);
}

void Union(int node1, int node2) {
	node1 = find(node1);
	node2 = find(node2);
	if (node1 == node2) return;

	if (node1 > node2) swap(node1, node2);
	parent[node2] = node1;
}

bool isUnion(int node1, int node2) {
	if (find(node1) == find(node2)) return true;
	else return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), M(0);
	cin >> N >> M;

	vector<Bridge>bridges(M);

	int start(0), end(0);
	cin >> start >> end;

	int island1(0), island2(0), limit(0);

	parent = vector<int>(N + 1, 0);
	for (int idx = 1; idx <= N; ++idx) parent[idx] = idx;

	for (int idx = 0; idx < M; ++idx) {
		cin >> bridges[idx].island1 >> bridges[idx].island2 >> bridges[idx].limit;
	}

	sort(bridges.begin(), bridges.end(), cmp);

	for (int idx = 0; idx < M; ++idx) {
		island1 = bridges[idx].island1;
		island2 = bridges[idx].island2;
		if (isUnion(island1, island2) == true) continue;
		else {
			Union(island1, island2);
			if (find(start) == find(end)) {
				cout << bridges[idx].limit;
				return 0;
			}
		}
	}
	cout << "0";
}