백준 BOJ 1939 - 중량제한

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

1939번: 중량제한

두 공장을 잇는 가중치의 최솟값이 최대가 되게 하는 문제.

이렇게말하니까 되게 어려워보인다;;

 

문제의 핵심은 중량제한이 낮은 다리는 굳이 건널 이유가 없다는 발상.

중량제한이 높은 다리들만 이용해서 두 공장을 연결할 수 있다면 정답에 쉽게 도달할 수 있을것이다.

 

"두 공장을 연결할 수 있다면"

>> 유니온파인드를 이용해서 두 공장이 연결됬는지 확인

 

"중량제한이 높은 다리들만 이용해서"

>> 중량제한이 높은 순서로 다리를 하나씩 연결해간다.

 

중량제한이 높은 순서로 다리를 연결해서

연결할때마다 두 공장이 서로 연결되었는지 확인해주면 된다.

다리의 연결은 유니온파인드의 두 연산 중 union() 을 이용하고,

두 공장의 연결 확인은 find()를 사용한다

 

BFS + 이분탐색으로도 풀수 있다는 듯 하지만

유니온파인드를 사용하는 풀이 쪽이 좀더 깔끔한 형태가 아닌가 싶다

 

BFS + 이분탐색 풀이는
이분탐색을 통해서 중량제한을 정해준 뒤에,
이분탐색으로 고른 값 mid보다 중량제한이 큰 도로만 지나면서 bfs를 수행해서
두 공장이 서로 연결될수있는지를 체크한다.

연결될 수 있다면 [mid+1,e] 범위에서, 연결될 수 없다면 [s,mid] 범위에서 재탐색

 

나는 유니온파인드로 풀었다 ㅎㅎ

소스코드 펼쳐보기

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

int parent[12345] = {0};
vector<pair<int,pair<int,int>>> v;

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

void joint(int a, int b){
	a = find(a);
	b = find(b);
	parent[a] = b;
	return;
}

int main(){
	for(int i=0; i<12345; i++) parent[i] = i;
	
	int N,M;
	int A,B;
	cin >> N >> M;
	for(int i=0; i<M; i++){
		int a,b,c;
		cin >> a >> b >> c;
		v.push_back({-c,{a,b}});
	}
	cin >> A >> B;
	
	sort(v.begin(), v.end());
	
	int ptr = 0;
	while(true){
		joint(v[ptr].y.x, v[ptr].y.y);
		if(find(A) == find(B)) break;
		ptr++;
	}
	
	cout << -v[ptr].x;
	return 0;
}