[BOJ/Gold 1] 백준 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번과 N번 컴퓨터를 잇는 것이 불가능 하다면 -1을 출력한다.

예제 입력 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

예제 출력 1

4

힌트

1-3 3-2 2-5을 이용하여 인터넷을 연결한다면 그 가격들은 4 3 9원이 나오게 된다.

하지만 코레스코에서 1개의 케이블은 무상으로 주니까 9원짜리를 뺀 것 중 가장 큰 가격은 4가 된다.

알고리즘 분류

• 이분 탐색
• 최단 거리 알고리즘

풀이

이분 탐색을 사용하여 특정한 가격을 넘는 인터넷 선에는 가중치를 부여한다. 따라서 Cost[N]은 1번 컴퓨터에서 N번 컴퓨터를 연결할 때 사용한 인터넷 선 중 특정한 가격이 넘는, 그러니까 무료로 연결해주는 인터넷 선의 개수를 의미한다.

이분 탐색과 다익스트라를 계속 사용하면서 Cost[N]이 K개 이하가 되게 하는 가격 중 최솟값을 찾는다.

이 글을 참고하는 게 더 나을 듯..

백준1800 인터넷 설치

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int N, P, K;
int LO = 0;
int HI = INF;
vector<pair<int, int> > Edge[MAX];
int Cost[MAX];
int answer = -1;

void Init() {
	for (int i = 1; i <= N; i++) {
		Cost[i] = INF;
	}
}

void Input() {
	cin >> N >> P >> K;
	for (int i = 0; i < P; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		Edge[A].push_back(make_pair(B, C));
		Edge[B].push_back(make_pair(A, C));
	}
}

bool Dijkstra(int X) {
	Init();
	priority_queue<pair<int, int> > PQ;
	Cost[1] = 0;
	PQ.push(make_pair(0, 1));

	while (!PQ.empty()) {
		int CurC = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextC = (Edge[CurX][i].second > X);
			// 이분 탐색을 사용하여 특정한 가격이 넘는 인터넷 선에는 가중치를 부여한다. 즉 가중치는 공짜로 연결해주는 인터넷 선의 개수를 의미한다.
			int nextX = Edge[CurX][i].first;
			if (Cost[nextX] > CurC + nextC) {
				Cost[nextX] = CurC + nextC;
				PQ.push(make_pair(-Cost[nextX], nextX));
			}
		}
	};

	return (Cost[N] <= K);
}

void Find_Answer() {
	while (LO <= HI) {
		int MID = (LO + HI) / 2;
		if (Dijkstra(MID)) {
			answer = MID;
			HI = MID - 1;
		}
		else {
			LO = MID + 1;
		}
	};
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}