[백준] 1939-중량제한(C++)

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

1939번: 중량제한

 

접근방식

 

1. 모든 경우를 판단해주어야 하는 것을 인지

2. 근데 n이 10000으로 크기 때문에 일반적인 bfs, dfs가 불가능함을 인지

3. 그러면 방문했던 값을 저장하는 dp(메모이제이션) 방식이 가능한가 확인

4. 10,000*10,000 = 100,000,000 X 4Byte = 대략 400Mb... 즉, dp방식도 불가능

5. 이분탐색을 통해서 방문하는 범위를 줄여볼까? 생각하게 됨

 

문제풀이 

 

1. 결과값은 다리의 비용중에 하나이다.2. 최소 비용(0), 최대비용(다리 비용중 최대값)을 low, high값으로 지정하고 mid값일때, 이동가능한지 확인3. 간단한 bfs를 통해서 이동이 가능한지 확인 4. 이동이 불가하면 high값을 낮춰주고, 이동이 가능하면 low값을 올려주며 진행

 

이분탐색 + bfs로 해결하는 문제입니다. 아래는 정답코드입니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int n, m;
int a, b, c;
vector <pair<int, int>> vec[10001];
bool visited[10001];
int s, e;
int bfs(int cost) {
	queue <int> que;
	que.push(s);
	visited[s] = 1;

	while (!que.empty()) {

		int cur = que.front();
		que.pop();
		if (cur == e)
			return true;
		for (int i = 0; i < vec[cur].size(); i++) {
			int ncur = vec[cur][i].first;
			int ncos = vec[cur][i].second;

			if (!visited[ncur] && ncos >= cost) {
				visited[ncur] = 1;
				que.push(ncur);

			}

		}



	}

	return false;

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	int from, to, cost;
	int maxcost = 0;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
		if (cost > maxcost)
			maxcost = cost;
	}
	
	cin >> s >> e;
	
	int low = 0, high = maxcost;
	while (low <= high) {
		
		memset(visited, 0, sizeof(visited));
		int mid = (low + high)/2;

		if (bfs(mid)) {
			low = mid  + 1;
		}
		else {
			high = mid  - 1;
		}
		
	}
	cout << high << endl;

	return 0;
}