[BOJ]1939번: 중량제한 (c++)

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

1939번: 중량제한

 

이분탐색 + dfs

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

bool dfs(vector<vector<pair<int, int>>>& graph, vector<bool>& visit, int from, int dest, int weight)
{
	// 도착하면 true반환
	if (from == dest)
	{
		return true;
	}
	
	// 현재위치 방문 체크
	visit[from] = true;
	
	// from의 인접 노드 탐색
	for (auto& bridge : graph[from])
	{
		int to = bridge.first;
		int limit = bridge.second;

		// 아직 방문하지 않았고, 현재 무게가 중량제한 이하라면
		if (!visit[to] && weight <= limit)
		{
			// 한번이라도 dest에 도달했다면 true반환
			if (dfs(graph, visit, to, dest, weight))
			{
				return true;
			}
		}
	}

	return false;
}

int binary_search(vector<vector<pair<int, int>>>& graph, int left, int right, int strt, int dest)
{
	int max_weight = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;

		// 중량이 mid 일 때, strt -> dest 이동이 가능하면 max_weight 갱신
		vector<bool> visit(graph.size());
		if (dfs(graph, visit, strt, dest, mid))
		{
			max_weight = mid;
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	return max_weight;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int limit_min = numeric_limits<int>::max();
	int limit_max = 0;

	// 입력 및 그래프 생성
	int N, M;
	cin >> N >> M;
	vector<vector<pair<int, int>>> graph(N + 1);
	for (int i = 0; i < M; ++i)
	{
		int from, to, limit;
		cin >> from >> to >> limit;

		graph[from].push_back(make_pair(to, limit));
		graph[to].push_back(make_pair(from, limit));

		// 무게 제한의 최소/최대값 구하기
		limit_min = min(limit, limit_min);
		limit_max = max(limit, limit_max);
	}
	int strt, dest;
	cin >> strt >> dest;

	// strt에서 dest로 이동할 때 가능한 최대무게를 이분탐색으로 찾기
	cout << binary_search(graph, limit_min, limit_max, strt, dest);

	return 0;
}

 

 

크루스칼, 정렬 등 여러가지 방법으로 풀이할 수 있는 문제이다. 

나는 시작점에서 끝점까지 dfs 탐색을 가능케 하는 최대무게를 이분탐색으로 찾는 방법으로 풀었다. 

 

풀이 전략은 간단하다. 

1. 가중치 있는 그래프 생성

2. 이분탐색으로 mid 설정

3. mid값으로 건널 수 있는 다리를 건너서 시적점에서 끝점까지 1번이라도 도달하면 true

 

 

그런데 3번에서 자꾸 시간초과가 났다.

서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며,

문제에서 위와 같은 조건이 주어졌음에도 백트랙킹으로 코드를 작성했기 때문이었다. 

[현재무게 <= 각 다리의 무게제한]인 조건을 만족해서 다음 섬으로 넘어갈수 있기만 하면 되므로,

두 섬간 연결된 모든 다리를 확인할 필요는 없었다.

따라서 방문한 지점에 true체크만 해주면 되고, 백트랙킹 코드를 작성하면 안된다!