백준 1939(중량제한)

www.acmicpc.net/problem/1939

1939번: 중량제한

dfs와 bfs의 차이점과 특징을 상기시켜준 문제. 

 

처음에는 그냥 dfs로 풀었다. 그러자 TLE

 

최악의 경우에 거의 N*M의 시간복잡도를 가지므로, 10^9 시간초과 발생가능성이 존재한다. 따라서 시간을 더 줄일 방법을 찾아야 했다. 단순 탐색으로 풀게된다면 dfs나 bfs나 똑같이 된다. 따라서 다른 방법이 필요했다. 

 

이진탐색을 이용해서 중량을 결정하고 탐색 가능 여부만 고르면 될까라고 생각을 했고, dfs+이분탐색으로 했지만 똑같이 TLE

 

생각을 해보니 dfs는 끝나지 않는다. 재귀함수는 전체를 통제시키는 어떤 것이 없다. 뭐 설정을 해주면 있기야 하겠지만.. 일단 기본적으로는 존재하지 않아서 그 경로까지 가는길을 찾더라도 다른길을 가보게 된다. 따라서 bfs로 풀었다. 

 

bfs는 queue에 넣어서 작동시키는 방법 재귀함수가 아닌 경우이기 때문에 한 함수에 대해서 종료만 시키면 모두 종료된다. 그래서 bfs로는 가능 여부가 더 쉽게 된다. 그리고 메모리 초과가 한 번 있었는데 단순하게 visited를 먼저 설정하느냐 후에 설정하느냐에 따라서도 메모리초과가 결정날 수 있겠구나 생각을 한다. 

 

후에 하게되면 중복된 index가 게속해서 들어갈 수 있게된다.  따라서 먼저하자 

 

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX 10005

vector<pair<int, int> > graph[MAX];
int start, fin;
bool check[MAX];

bool bfs(int weight) {
	queue<int> q;
	q.push(start);
	check[start] = true;
	while (!q.empty()) {
		int num = q.front();
		q.pop();
		for (int i = 0; i < graph[num].size(); i++) {
			if (check[graph[num][i].first] || graph[num][i].second < weight)continue;
			if (graph[num][i].first == fin) {
				return true;
			}
			check[graph[num][i].first] = true;
			q.push(graph[num][i].first);
		}
	}
	return false;
}

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));

	}
	cin >> start >> fin;


	int right = 1000000000, left = 1, mid, ans = 0;

	while (right >= left) {
		for (int i = 0; i < MAX; i++)check[i] = false;
		mid = (right + left) / 2;
		if (bfs(mid)) {
			left = mid + 1;
			ans = mid;
		}
		else {
			right = mid - 1;
		}
	}
	cout << ans << '\n';
}