[BOJ] 백준 1939 중량제한 c++ (이분탐색, bfs)

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

1939번: 중량제한

---

풀이

공장을 운영할 섬 2개가 주어지고, 물품들의 중량의 최댓값을 구하는 문제이다.

 

이분탐색으로 중량의 최댓값 찾기

대부분의 이분탐색 코드는 아래와 유사하다.

left, right를 두고 mid 값을 찾은뒤, mid 값이 조건에 일치하면 left 값을 mid +1, 그렇지 않으면 right 값을 mid-1로 변경한다.

while(left <= right) {
    int mid = (left + right) / 2;

    if(cal(mid)) {
        ans = max(ans, mid);
        left = mid + 1;
    }
    else right = mid - 1;
}

이제 mid 값이 조건(두 섬간에 이동이 가능한지)에 일치하는지 찾아주는 cal 함수를 구현하자.

 

bfs으로 중량제한 확인하기

bfs를 사용한 이유는, 중량을 초과하지 않고 두 섬간 이동이 가능한지 확인만 하면 되기 때문에 bfs를 사용하였다.

연결된 문제를 풀때 자주 사용 하는 방법처럼 처음 입력을 받을때 vector의 양쪽에 정보를 push를 해준 후,

bfs를 통해 목표지점을 찾아나가면 된다.

vector<pair<int, int>> bridge[10001]; // next, cost

bool cal(int mid) {
	queue<int> q;
	q.push(company.first);

	while(!q.empty()) {
		int now = q.front();
		q.pop();
		check[now] = true;

		if(now == company.second) {
			return true;
		}

		for(int i = 0; i < bridge[now].size(); i++) {
			int next = bridge[now][i].first;
			int weight = bridge[now][i].second;

			if(mid <= weight && !check[next]) {
				check[next] = true;
				q.push(next);
			}
		}
	}
	return false;
}

아래 코드에서 방문 배열(check)의 초기화는 이분탐색 while문 내에서 처리하였다.

---

코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<pair<int, int>> bridge[10001];
pair<int, int> company;
bool check[10001];
int ans;

bool cal(int mid) {
	queue<int> q;
	q.push(company.first);

	while(!q.empty()) {
		int now = q.front();
		q.pop();
		check[now] = true;

		if(now == company.second) {
			return true;
		}

		for(int i = 0; i < bridge[now].size(); i++) {
			int next = bridge[now][i].first;
			int weight = bridge[now][i].second;

			if(mid <= weight && !check[next]) {
				check[next] = true;
				q.push(next);
			}
		}
	}
	return false;
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N >> M;
	int maxWeight = 0;
	for(int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		maxWeight = max(maxWeight, c);

		bridge[a].push_back({b, c});
		bridge[b].push_back({a, c});
	}
	cin >> company.first >> company.second;

	int left = 1;
	int right = maxWeight;

	while(left <= right) {
		int mid = (left + right) / 2;

		if(cal(mid)) {
			ans = max(ans, mid);
			left = mid + 1;
		}
		else right = mid - 1;
		memset(check, false, sizeof(check));
	}
	cout << ans << '\n';
	return 0;
}