BOJ 1800 인터넷 설치 / C++

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

1800번: 인터넷 설치

백준 온라인저지 1800번 인터넷 설치 문제입니다.

 

아이디어

해당 문제를 혼자만의 힘으로 풀어내지는 못했습니다. 다익스트라를 이용하여 간선의 가중치를 관리해야한다는 것은 알고 있었지만 최소 목표비용 선정하여 다익스트라를 튜닝하는 방법은 상상치도 못했죠.. 아래는 간단한 문제 풀이입니다.

먼저 최소 목표 비용을 선정하고 해당 값이 매개변수 탐색을 이용하여 조건을 만족할시 정답이 됩니다.

여기서 조건은 1부터 N까지의 다익스트라를 돌리는데 최초 1의 가중치를 0으로 잡고 최소 목표비용보다 큰 숫자가 있을때 마다 1을 더해주어 N까지 도달하기까지 노드간 가중치 비용이 최소 목표비용를 넘는 노드의 개수를 파악하고, 최소 목표비용보다 큰 비용이 필요한 노드의 개수가 K보다 작으면 조건에 만족하게 됩니다. 이렇게 되면 최소 목표비용 보다 큰 노드의 비용은 공짜(K)로 연결 할 수 있기 때문입니다.

이제 백준 문제도 200개 넘게 풀었는데 이 정도로 고차원적인 생각을 해야하는 문제는 처음 만나서 당황스럽기도 하면서 비슷한 문제들을 많이 풀어 익숙하게 만들어야 한다는 생각도 듭니다. 추석내내 고민하여 성장할 수 있는 원동력을 찾은 것 같아서 헛된 시간만은 아니라고 느껴지네요. 열심히 성장합시다.

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 987654321
using namespace std;

int N, P, K, maxCost;
vector<vector<pair<int,int>>> node;
void input() {
	cin >> N >> P >> K;
	node.resize(N + 1);
	for (int i = 0; i < P; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		node[a].push_back({ b,c });
		node[b].push_back({ a,c });
		maxCost = max(maxCost, c);
	}
}

bool dijkstra(int target) {
	vector<int> cost(N + 1, MAX);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, 1 });
	cost[1] = 0;
	while (!pq.empty()) {
		int currentNode = pq.top().second;
		int currentCost = pq.top().first;
		pq.pop();
        
		if (cost[currentNode] < currentCost)  continue;

		for (int i = 0; i < node[currentNode].size(); i++) {
			int nextNode = node[currentNode][i].first;
			// 최소 가중치를 넘는 간선에는 1부여 아닐 경우 0으로 표시
			int nextCost = currentCost + (node[currentNode][i].second > target); 
			if (nextCost < cost[nextNode]) {
				cost[nextNode] = nextCost;
				pq.push({ nextCost ,nextNode });
			}
		}
	}
	return (cost[N] <= K); // 최소 가중치를 넘는 간선이 K개를 넘는지 확인
}
//매개변수 탐색 - 목표 최소 비용 결정
int binarySearch(int l, int r) {
	int mid;
	int sol = -1;
	while (l <= r) {
		mid = (l + r) / 2;
		if (dijkstra(mid)) {
			r = mid - 1;
			sol = mid;
		}
		else
			l = mid + 1;
	}
	return sol;
}

//특정 가중치 이하의 간선으로만 경로를 구성할 수 있는지 판단해야 하는 문제
void solution() {
	cout << binarySearch(0, maxCost);
}
int main(void) {
	input();
	solution();
}
//https://www.acmicpc.net/problem/1800