[백준/BOJ] 백준 1800번 : 인터넷 설치

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

1800번: 인터넷 설치

이분 탐색을 이용해서 해당 비용으로 1번부터 N번까지 연결이 가능한지 확인하여 최소 비용을 찾았다. 해당 비용으로 1번부터 N번까지 연결이 가능한지 확인하는 방법은 해당 간선의 가격이 현재 확인하는 비용보다 큰 연결일 때 간선을 카운트하고, 현재 확인하는 비용보다 작은 연결일 때는 간선을 카운트하지 않는 방법으로, N번까지 가는 길중 가장 최소 간선 카운트 개수를 다익스트라를 이용해 구해서 N번까지 연결이 되었을 때 카운트된 간선의 수가 K이하인지 확인하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int n, p, k;
vector<pair<int, int>> adj[1001];
int max_value = 0;

//cost비용이하로 1번부터 n번까지 인터넷선을 연결할 수 있는지 확인
bool Solve(int cost)
{
	vector<int> result(1001, 987654321); //[위치] = 해당 위치로 오는데 연결한 간선의 최소 개수
	priority_queue<pair<int, int>> pq;

	result[1] = 0;
	pq.push(make_pair(-0, 1));

	while (!pq.empty())
	{
		int here_cnt = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		if (result[here] < here_cnt)
			continue;

		//n까지 연결했을때
		if (here == n)
		{
			if (here_cnt <= k)
				return true;

			else
				return false;
		}

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there_cnt = here_cnt;
			int there = adj[here][i].second;
			int this_cost = adj[here][i].first;

			//cost보다 비용이 큰 연결일때
			if (this_cost > cost)
			{
				there_cnt++;
			}

			if (result[there] > there_cnt)
			{
				result[there] = there_cnt;
				pq.push(make_pair(-there_cnt, there));
			}

		}
	}

	//n에 도달하지 못할때
	return false;
}

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

	cin >> n >> p >> k;

	for (int i = 0; i < p; i++)
	{
		int u, v, cost;
		cin >> u >> v >> cost;

		adj[u].push_back(make_pair(cost, v));
		adj[v].push_back(make_pair(cost, u));

		max_value = max(max_value, cost);
	}

	int left = 0;
	int right = max_value;
	int result = -1;

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

		if (Solve(mid) == true)
		{
			result = mid;

			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	cout << result;

	return 0;
}