[백준][C++] 1939: 중량제한

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

 

처음엔 그냥 무식하게 bfs + 인접행렬로 풀어봤더니 당연하게도 메모리 초과가 나옵니다. 노드가 10000개이기 때문에 인접행렬로 만들면 메모리 초과가 나옵니다. 인접 리스트(adjacency list)로 풀어야 합니다.

이 문제의 핵심은 이분탐색(Binary Search)입니다. 문제 입력 중에 중량제한으로 입력된 값 중 하나가 답이겠죠? 이 값 중 가장 큰 값을 찾으면 그게 답입니다. 그 값을 효율적으로 찾으려면 binary search를 써야 하고요.

 

\begin{align}
low&=0 \\
high&=\text{중량제한 중 최대값} \\
mid&=(low+high)/2
\end{align}

이렇게 설정하고, \(mid\) 값에 대해 bfs를 돌려서 도달 가능한지 아닌지 확인하면 됩니다.

자세한 건 아래 코드를 참조하세요

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

int n, m;
int start, dest;
vector<pair<int, int>> bridges[10001];	// <to, cost>
bool visited[10001];


bool bfs(int cost) {
	//cost의 무게가 목적지까지 갈 수 있는지 반환

	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int curr = q.front();
		q.pop();

		if (curr == dest)
			return true;

		for (auto& p : bridges[curr]) {
			int next_idx = p.first;
			int next_cost = p.second;

			if (!visited[next_idx] && cost <= next_cost) {
				q.push(next_idx);
				visited[next_idx] = true;
			}
		}
	}

	return false;
}


int main(int argc, char** argv)
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	cin >> n >> m;

	int a, b, c;
	
	int low=0, high=0;
	for (int i = 0; i < m; ++i) {
		cin >> a >> b >> c;
		bridges[a].push_back(make_pair(b, c));
		bridges[b].push_back(make_pair(a, c));
		high = max(high, c);
	}

	cin >> start >> dest;
	int mid;
	while (low <= high) {
		mid = (low + high) / 2;

		memset(visited, 0, sizeof(visited));
		if (bfs(mid))
			low = mid + 1;
		else
			high = mid - 1;
	}

	cout << high;
	
	

	return 0;
}

dfs는 visited node 체크가 안돼서 안됩니다. 물론 memoization 추가해주면 상관 없습니다.

사실 이 문제는 그냥 크루스칼 쓰시면 됩니다.. 대신 edge 정렬할 때 조건을 바꿔서 내림차순으로 정렬해야 maximum spanning tree가 나오니까 그 점 유의하시면 됩니다.