[백준] #1800번 인터넷 설치 (C++)

오진서·2022년 2월 20일
3

문제

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


본인이 처음 시도한 방식

문제를 보고 처음 접근한 방식은 위와 같은 예제 입력1 그래프가 있을 때 한 정점에서 다른 한 정점까지의 (조건이 추가된) K번 째 최단 거리를 구하면 된다고 생각하였다.

그래서 DFS를 이용한 완전 탐색으로 각 인접 정점으로 접근하여 이전 정점에서 현재 정점까지의 거리를 우선순위 큐에 삽입 연산을 거치고, N번 째 정점에 도달하였을 때 우선순위 큐에서 K만큼 pop한 결과 값 중 가장 최솟값이 답일 것이라고 생각하였다.

그런데 문제가 있었다.

완전 탐색을 수행할려면 우선순위 큐에서 push한 값을 복귀하는 과정(pop)도 필요한데 힙의 삭제 연산은 힙 정렬과도 같기 때문에 O(logN)의 시간복잡도가 나온다.

어림잡아 최악의 경우를 생각해보았을 때 0이 10개 나오는 것을 보고 바로 패스했다.

문제를 뚫어져라 봐도 답이 안보여 힌트를 얻고자 알고리즘 분류를 봤는데 다익스트라와 이분탐색..? 도저히 답이 안보여 구글링을 하게 되었다.



풀이

문제의 핵심은 주어진 x 값 이하의 간선으로 구성된 최단 경로를 구성할 수 있는지에 대한 여부를 결정하는 것이 관건인 문제이다.

문제의 답을 보면 원장이 내는 최소의 비용을 구하는 문제이다.

즉, 문제에 주어진 비용의 최댓값이 1,000,000이고 이진 탐색을 통해 원장이 낼 수 있는 최소의 비용을 탐색하며, 찾는 과정에서 다익스트라 알고리즘으로 검증을 해나가야 한다.

핵심은 다익스트라 알고리즘을 통해 어떻게 검증하느냐인데 이진 탐색에서 넘겨진 비용을 X라고 했을 때, 간선의 비용이 X보다 크다면 해당 노드의 비용을 1로 정한다.

그러면 dist 배열에 X비용보다 비싼 간선의 개수가 저장되므로 dist[N]에는 x비용보다 비싼 간선의 총 갯수가 담기게 된다.

그리고 dist[N] 값이 K보다 크다면 해당 X 값 이하의 값으로 경로를 구성하지 못한다는 의미이므로 오른쪽 탐색을 실행한다.

사실 코드를 보는게 훨 이해가 빠르게 될 것이다..



코드

#include<iostream>
#include<queue>
#include<vector>
#include <string.h>
#define MAXN 1001

using namespace std;

int n, p, k;
vector<pair<int, int>> graph[MAXN];
int dist[MAXN];

// x이하의 간선으로 구성된 최단 경로를 구성할 수 있는지?
bool dijkstra(int x) {
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, 1));

	while (!pq.empty()) {
		int cnode = pq.top().second;
		int cweight = -1 * pq.top().first;

		pq.pop();

		if (dist[cnode] < cweight) continue;

		for (int i = 0; i < graph[cnode].size(); i++) {
			int nnode = graph[cnode].at(i).first;
			int nweight = graph[cnode].at(i).second;

			// 핵심!!
			int w = cweight + (nweight > x);
			if (dist[nnode] > w) {
				dist[nnode] = w;
				pq.push(make_pair(-1*w, nnode));
			}
		}
	}

	return dist[n] <= k;
}

int main() {
	cin >> n >> p >> k;
	for (int i = 0; i < p; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back(make_pair(v, w));
		graph[v].push_back(make_pair(u, w));
	}

	int l = 0, r = 1e7, ans = -1;

	while (l <= r) {
		int mid = (l + r) >> 1;
		memset(dist, 0x3f, sizeof dist);
		dist[1] = 0;

		// true일 경우 mid 값 이하의 값으로 경로를 구성할 수 있으므로 왼쪽 탐색
		if (dijkstra(mid)) {
			r = mid - 1;
			ans = mid;
		}
		else { // false일 경우 mid 값 이하의 값으로 경로를 구성 못하므로 오른쪽 탐색
			l = mid + 1;
		}
	}

	cout << ans;
}

회고

골드 1의 벽을 뼈저리게 느낀 문제였다..
문제 풀이를 보고도 머릿속으로 겨우 이해가 되는데 과연 이와 비슷한 문제가 주어졌을 때 스스로 접근할 수 있느냐가 의문이다;

골드 1~2 이상 부터는 뭔가 고차원적 사고 기능을 요구하는데 이게 과연 노력으로 커버할 수 있을까..?


참고

https://batory.tistory.com/371

profile
안녕하세요

0개의 댓글