백준 1939번 | 중량제한 (C++ 풀이)

  문제  

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

1939번: 중량제한

---

  풀이  

• 사용 알고리즘 : 그래프 탐색(BFS) + 파라메트릭 서치
• 시간 복잡도 : O((N + M) * log(max(K)))

그래프 탐색 + 파라메트릭 서치를 이용하여 풀었습니다.

​

먼저 Naive한 풀이를 생각해 봅시다.

섬과 다리의 정보를 받아서 양방향 그래프화 시킵니다. 그 후 옮길 물품들의 중량을 k라고 했을 때, 섬 A에서 섬 B까지 이동할 수 있는 경로가 존재하는지 탐색해 주면 됩니다. 하지만 이 문제에서는 k가 1~10억이라는 범위를 가지고 있기 때문에 문제가 됩니다. 우리는 k의 최대를 구해야 하므로, 각 k마다 그래프 탐색을 한 번씩은 해봐야 하기 때문에 그 시간복잡도가 O(max(k) * (N + M))이 되겠죠. 따라서 최적화를 할 필요가 있습니다.

​

이때 사용해 볼 만한 테크닉이 바로 파라메트릭 서치입니다.

조금 관점을 달리해서 문제를 봐보죠. k의 최대를 구하는 데에 중점을 두지 말고, 우리가 임의의 k를 정한 뒤, 해당 k에 대해 그래프 탐색이 가능한지를 보는 겁니다.

우리가 임의대로 정한 어떤 k에 대해서 그래프 탐색을 돌려봅니다. 이때 만약 탐색이 가능했다면, k보다 더 큰 중량을 시도해 보는 거죠.

반대로 만약 k일 때 중량제한으로 인해 탐색이 불가능하다면, k보다 더 적은 중량을 시도해 보는 겁니다.

논리의 흐름을 보시면 느끼시겠지만, 마치 이분 탐색의 흐름 같죠? 실제로 파라메트릭 서치는 이분 탐색을 기반으로 한 테크닉입니다.

​

이 문제를 풀기 위해서는 k를 이분 탐색을 이용해서 찾아내야 합니다.

초기 low 값을 1, high 값을 10억으로 준 뒤, k를 mid 값((low + high) / 2)으로 두고 그래프 탐색을 진행합니다.

만약 그래프 탐색이 가능하다면, k의 값을 더 올려서 시도해 볼 만하므로 low 값을 mid + 1 값으로 바꿔주고 새로운 mid 값을 갱신하여 k에 넣어줍니다. 추가적으로 우리는 결국 k의 최대를 구해야 하므로, 구해야 하는 답의 max값을 계속 갱신해 주어야 합니다.

만약 그래프 탐색이 불가능하다면, k의 값을 더 낮춰야 하므로 high 값을 mid - 1 값으로 바꿔주고 k 값을 갱신해 주면 됩니다.

​

결과적으로, 이분 탐색을 이용해 k의 최대를 구하는 데에는 O(log(1e9)) 시간 안에 해결이 될 겁니다. 그리고 각각의 k에 대해 그래프 탐색을 진행해 줘야 하므로, 이 문제는 O(log(1e9) * (N + M)) 시간 안에서 해결 가능합니다. 최악의 경우에도 연산량이 40만 번을 넘지 못합니다.

---

  코드  

#include <bits/stdc++.h> 
using namespace std;
const int INF = 2e9;
const int inf = 1e9;

vector<pair<int, int> > v[100001]; // node, cost
bool visited[100001];

int bfs(int i1, int i2) {
	int lo = 1;
	int hi = 1e9;
	int mid;
	int ret;
	
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		
		for (int i = 0; i < 100001; i++) visited[i] = false;
		
		queue<int> que;
		que.push(i1);
		visited[i1] = true;
		bool canMore = false;
		
		while (!que.empty()) {
			int node = que.front();
			que.pop();
			if (node == i2) {
				// mid 의 무게로 i1 - i2로 도착한 상황
				 canMore = true;
				 break;
			}
			
			for (int i = 0; i < v[node].size(); i++) {
				int next = v[node][i].first;
				int cost = v[node][i].second;
				if (visited[next]) continue;
				if (mid > cost) continue;
				visited[next] = true;
				que.push(next);
			}
		}
		if (canMore) {
			// 더 무겁게 가능? 
			lo = mid + 1;
			ret = mid;
		}
		else {
			// 더 가볍게 가능?
			hi = mid - 1; 
		}
	}
	return ret;
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		// 양방향 그래프화 
		v[a].push_back({b, c});
		v[b].push_back({a, c});
	}
	int i1, i2;
	cin >> i1 >> i2;
	int ans = bfs(i1, i2);
	cout << ans;
	return 0;
}