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

문제 링크: www.acmicpc.net/problem/1800

1800번: 인터넷 설치

1. 주의할 점

- 이분탐색 + 다익스트라를 이용하여 문제를 해결한다

 

2. 구현

- 2가지의 방법으로 풀었으며, 다익스트라는 우선순위큐를 활용하여 푸는 방법이 훨씬 빠르다

- Result의 값은 -1로 초기화한다(N번 컴퓨터까지 도달하지 못할 경우를 대비)

- Dijkstra() 함수만 바뀐다

- 메인 함수에서 케이블선에 대한 정보를 받을 때, 케이블선의 최대 가격을 R에 저장한다

- L은 0에서부터 시작한다. 1에서 시작하면 다음과 같은 반례가 존재한다

5 7 4
1 2 9 
3 1 9 
2 4 9 
3 2 9 
5 2 9 
3 4 9 
4 5 9

답: 0

 

[단순 다익스트라 - BFS] - 632ms

- 구조체를 활용하며, Remain(= P - Mid보다 높은 가격의 케이블선 수)을 통해 N번 컴퓨터까지 연결할 수 있는지 확인해본다

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
	int idx, val, remain;
};
info tmp;
int node, edge, p;
vector<info> v[1001];
int visit[1001];

bool dijkstra(int mid) {
	queue<info> q;
	for (int i = 1; i <= node; i++)
		visit[i] = -1;
	tmp.idx = 1;
	tmp.remain = p;
	q.push(tmp);
	while (!q.empty()) {
		int cidx = q.front().idx;
		int cr = q.front().remain;
		q.pop();
		if (cidx == node)
			return true;
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i].idx;
			int nv = v[cidx][i].val;
			if (visit[next] >= cr) continue;
			if (nv > mid) {
				if (cr == 0) continue;
				tmp.remain = cr - 1;
				visit[next] = cr - 1;
			}
			else {
				tmp.remain = cr;
				visit[next] = cr;
			}
			tmp.idx = next;
			q.push(tmp);
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int l = 0, r, mid, a, b, val, result = -1;
	cin >> node >> edge >> p;
	for (int i = 0; i < edge; i++) {
		cin >> a >> b >> val;
		tmp.val = val;
		tmp.idx = b;
		v[a].push_back(tmp);
		tmp.idx = a;
		v[b].push_back(tmp);
		r = max(r, val);
	}
	while (l <= r) {
		mid = l + (r - l) / 2;
		if (dijkstra(mid)) {
			r = mid - 1;
			result = mid;
		}
		else
			l = mid + 1;
	}
	cout << result;
	return 0;
}

 

[우선순위 큐를 이용한 다익스트라] - 4ms

- Dist[] 배열을 사용하며, Dist[] 배열은 해당 컴퓨터까지 도달했을 때, Mid보다 큰 값을 가졌던 케이블의 수를 저장하고 있다

- Val 값의 오름차순에 따라 우선순위큐를 설정한다

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
	int idx, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
int node, edge, p;
vector<info> v[1001];
int dist[1001];

bool dijkstra(int mid) {
	priority_queue<info, vector<info>, cmp> pq;
	tmp.idx = 1;
	tmp.val = 0;
	pq.push(tmp);
	for (int i = 1; i <= node; i++)
		dist[i] = 987654321;
	dist[1] = 0;
	while (!pq.empty()) {
		int cidx = pq.top().idx;
		int cv = pq.top().val;
		pq.pop();
		if (dist[cidx] < cv) continue;
		for (int i=0; i<v[cidx].size(); i++) {
			int next = v[cidx][i].idx;
			int nv = cv + (v[cidx][i].val > mid);
			if (nv < dist[next]) {
				dist[next] = nv;
				tmp.idx = next;
				tmp.val = nv;
				pq.push(tmp);
			}
		}
	}
	return dist[node] <= p;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int l = 0, r, mid, a, b, val, result = -1;
	cin >> node >> edge >> p;
	for (int i = 0; i < edge; i++) {
		cin >> a >> b >> val;
		tmp.val = val;
		tmp.idx = b;
		v[a].push_back(tmp);
		tmp.idx = a;
		v[b].push_back(tmp);
		r = max(r, val);
	}
	while (l <= r) {
		mid = l + (r - l) / 2;
		if (dijkstra(mid)) {
			r = mid - 1;
			result = mid;
		}
		else
			l = mid + 1;
	}
	cout << result;
	return 0;
}