BOJ - 1939번 중량제한(C++)

문제 출저: https://www.acmicpc.net/problem/1939

문제 난이도

Gold 4

문제 접근법

문제를 이해부터 하는게 관건.
즉, 시작점에서 끝점까지 물건을 이동하는데 다리 중량 제한을 넘지 않는 무게 중 최대값을 구하라는 것이다. (문제 중 한번의 이동이 힌트)
시작점과 끝점까지를 탐색해서 무게가 넘지 않는지 check하고 그 중 가장 큰 값을 찾으면 되기 때문에 탐색이 필요하다.
이 때, 이분 탐색을 이용한다.

통과 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>


using namespace std;

struct bridge {
	int node, weight;
	bridge(int n, int w) {
		node = n;
		weight = w;
	}

};

vector<bridge> arr[10001];
int N, M;
bool ch[10001];
int s,f;

bool isPass(int weight) {
	memset(ch, false, sizeof(ch));
	ch[s] = true;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (cur == f) return true;
		for (int i = 0; i < arr[cur].size(); i++) {
			int next = arr[cur][i].node;
			int nextW = arr[cur][i].weight;
			if (ch[next] || weight > nextW) continue;
			q.push(next);
			ch[next] = true;
		}
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	int maxWeight = 0;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[a].push_back(bridge(b, c));
		arr[b].push_back(bridge(a, c));
		maxWeight = max(maxWeight, c);
	}
	cin >> s >> f;

	int low = 0, high = maxWeight;
	int ans = 0;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (isPass(mid)) {
			ans = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
	cout << ans << "\n";
	
	return 0;
}

기타

처음에 문제를 이해못하고 제한 내에서의 가장 큰 값인 줄 알고 다익스트라를 응용해서 다리의 무게 최대값을 찾았다. 그것도 중량의 더한값으로.. 큐를 이용해서 탐색을 하기도 하면서 계속 틀렸습니다가 뜨길래 다른 풀이를 보고 문제를 이해할 수 있었다.
알고리즘은 문제에 적절한 알고리즘으로 푸는 것도 중요한데 가끔 문제를 이해를 잘못해서 못푸는 경우가 있다. 역시 답은 문제를 많이 풀어봐야하는 건가..