[BOJ/백준 1800/C++] 인터넷 설치

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

1800번: 인터넷 설치

 

[문제 요약]

- 각각의 학생들의 번호가 1부터 N까지 붙여져 있다고 하면 아무나 서로 인터넷 선이 연결되어 있지 않다. P(P<=10,000)개의 쌍만이 서로 이어 질수 있으며 서로 선을 연결하는데 가격이 다르다.

 

- 1번은 다행히 인터넷 서버와 바로 연결되어 있어 인터넷이 가능하다.

 

- 우리의 목표는 N번 컴퓨터가 인터넷에 연결하는 것이다. 나머지 컴퓨터는 연결 되어 있거나 연결 안되어 있어도 무방하다.

 

- 하지만 코레스코에서는 K개의 인터넷 선에 대해서는 공짜로 연결해주기로 하였다. 그리고 나머지 인터넷 선에 대해서는 남은 것 중 제일 가격이 비싼 것에 대해서만 가격을 받기로 하였다.

 

- 이때 원장선생님이 내게 되는 최소의 값을 구하여라.

 

[문제 조건]

- 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다.

 

- 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차례로 들어온다. 가격은 1 이상 1,000,000 이하다.

 

[문제 풀이]

처음에 문제를 읽고 다양한 방법을 시도해봤지만 도저히 이 문제를 정확히 풀만한 방법이 떠오르지 않아 구글링을 통해 힌트를 얻었다.

 

이 문제는 이분탐색을 통한 검증하는 방법으로 답을 구하는 문제였다.

 

문제를 읽고 "다익스트라를 이용해야 되겠구나" 라는 것까지는 생각을 했었는데 아직 이번 문제와 같이 이분 탐색을 이용해야 된다는 것까지는 아직 실력이 부족하다.

 

해결법은 다음과 같다.

• 1 ~ 1,000,000 의 초기 범위로 이분 탐색을 이용해 x원을 구한다.
• x원을 기준으로 다익스트라를 돌렸을 때 1에서 N번까지 경로 중 x보다 큰 간선의 개수가 K개 이하면 가능, K개 이상이면 불가능 ( 가능의 경우 right = mid - 1, 불가능의 경우 left =  mid + 1 )

이때 중요한 점은 다익스트라를 이용해 답을 구할 때 x원 이상의 간선들은 가중치를 1로 두고 이하의 간선들은 0으로 두면 배열에 저장된 값들은 경로들 중 간선의 비용이 x원 이상인 간선의 개수를 의미한다. 

 

따라서 dijk[N]의 값이 K보다는 작아야 x원으로 1번 부터 N번까지 연결 할 수 있다는 것이다. 우리가 구해야하는 것은 x의 최소값이므로 이 값을 적절히 조절하면 답을 구할 수 있따.

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

#define pii pair<int,int>
#define INF 987654321
using namespace std;

int N, P, K;
vector<vector<pii>> adj;
vector<int> dijk;

bool isPossible(int val)
{
	priority_queue<pii> pq;
	for (int i = 0; i < dijk.size(); i++) dijk[i] = INF;
	dijk[1] = 0;
	pq.push({ 1,0 });
	while (!pq.empty())
	{
		pii tmp = pq.top(); pq.pop();
		int cur = tmp.first;
		int cur_cost = -tmp.second;

		if (dijk[cur] < cur_cost) continue;

		for (int i = 0; i < adj[cur].size(); i++)
		{
			int tmp = 0;
			int next = adj[cur][i].first;
			int next_cost = adj[cur][i].second;

			if (next_cost > val) tmp = cur_cost + 1;
			else tmp = cur_cost;

			if (dijk[next] > tmp)
			{
				dijk[next] = tmp;
				pq.push({ next,-tmp });
			}

		}
	}

	if (dijk[N] <= K) return true;
	else return false;
}

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

	cin >> N >> P >> K;
	adj.resize(N + 1);
	dijk.resize(N + 1);
	for (int i = 0; i < P; i++)
	{
		int s, e, c;
		cin >> s >> e >> c;

		adj[e].push_back({ s,c });
		adj[s].push_back({ e,c });
	}

	int left = 0;
	int right = 1000000;
	int answer = -1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (isPossible(mid))
		{
			answer = mid;
			right = mid - 1;
		}
		else
			left = mid + 1;
	}
	cout << answer;
}

굳