백준 1939번 중량제한 (C++)

하루만에 멘탈이 다시 나가버렸다.
너무 어려운데 어떡해....? 하....

문제링크

https://www.acmicpc.net/problem/1939

설명

bfs와 이분 탐색을 이용하여 출발지점부터 도착지점까지 옮길 수 있는 중량의 최댓값을 구하는 문제이다.

맨 처음 다익스트라로 구현했는데 최솟값을 구하는 다익스트라로는 이 문제를 풀 수 없기 때문에 다시 생각했다.

1부터 6까지의 답이 8일 때, 다익스트라는 1부터 6까지의 경로 중 7이 있다면 7을 답으로 반환함

두뇌 풀가동하면서 어떻게든 풀어볼려다가 결국 실패하고 질문글이랑 다른 코드 찾아보았다.

우선 이 문제는 O(log n * (V + E))의 시간복잡도로 해결 가능하다.
이분탐색의 시간 복잡도가 0(log n)이고 이 문제에서는 최대 중량이 10억이므로 이분 탐색은 최대 30번 진행된다.

인접리스트로 구현한 bfs의 시간 복잡도가 O(V + E)이므로 시간 안에 해결 가능하다.

풀이 아이디어는 지금까지 이분 탐색에서 계속 언급한 파라메트릭 서치이다.

중량을 입력할 때 미리 최대 중량을 저장해둔 뒤, 중량을 기준으로 이분 탐색을 실행한다.

그리고 설정된 중량으로 bfs를 실행해 목적지까지 도달 가능한 지 확인한다.

목적지까지 도착이 가능하다면 더 높은 중량에서도 가능한 지 확인한다.
목적지까지 도착이 불가능하다면 중량을 낮게 설정해서 다시 확인한다.

요즘 골드 이상 난이도의 거의 모든 문제를 온전히 내 힘으로 푸는데 실패하고 있다. 여러모로 멘탈이 탈탈 털리지만... 이 또한 지나가리... 좀 더 노력해보자...^^

코드

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

using namespace std;
vector<pair<int, int>> bridge[10001];

bool bfs(int mid, int n, int a, int b)
{
	queue<int> q;
	vector<int> visited(n + 1);
	visited[a] = 1;
	q.push(a);
	while (!q.empty())
	{
		int pos = q.front();
		q.pop();

		if (pos == b)
			return true;

		for (int i = 0; i < bridge[pos].size(); i++)
		{
			int w = bridge[pos][i].first;
			int npos = bridge[pos][i].second;
			if (!visited[npos] && w >= mid)
			{
				visited[npos] = 1;
				q.push(npos);
			}
		}
	}
	return false;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, start, end, maxw = 0, mid, w, a, b;
	cin >> n >> m;
	while (m--)
	{
		cin >> start >> end >> w;
		bridge[start].push_back({ w,end });
		bridge[end].push_back({ w,start });
		maxw = max(w, maxw);
	}
	cin >> a >> b;
	start = 0;
	end = maxw;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (bfs(mid, n, a, b))
			start = mid + 1;
		else
			end = mid - 1;
	}
	cout << end;
	return 0;
}