알고리즘 문제해결 전략 Chapter 30 - ROUTING(C++)

예제: 신호 라우팅

위 그림은 여러 개의 컴퓨터들과 각 컴퓨터들을 잇는 회선을 나타냅니다. 각 회선들은 각각 품질이 다르며, 각 회선을 지날 때마다 신호에 있던 노이즈가 증폭될 수 있습니다. 각 회선에 쓰여 있는 글자는 해당 회선을 지날 때 노이즈가 몇 배 증폭되는가를 보여줍니다. 특정 컴퓨터에서 다른 컴퓨터로 메시지를 보내고 싶습니다. 이 때 노이즈의 증폭을 최소화하는 프로그램을 작성하세요.

입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어집니다. 각 테스트 케이스의 첫 줄에는 컴퓨터의 수 N (<= 10000) 과 회선의 수 M (<= 20000) 이 주어집니다. 각 컴퓨터는 0 부터 N-1 까지의 번호로 표현됩니다. 그 후 줄에 각 3개의 정수로 각 회선의 정보가 주어집니다. 회선의 정보는 a b c 로 표현되며, 이 때 이 회선은 a 번과 b 번 컴퓨터 사이를 이으며 이 회선을 지날 때 노이즈는 c 배 증폭됩니다. c 는 언제나 1 이상의 실수입니다. 모든 회선은 양방향으로 데이터를 전송할 수 있습니다.

시작 컴퓨터는 항상 0 번, 끝 컴퓨터는 항상 N-1번이라고 가정하며, 이와 같은 경로는 언제나 존재한다고 가정합니다.

출력
각 테스트 케이스마다, 노이즈가 최소화되는 경로에서 노이즈는 몇 배로 증폭되는지를 소숫점 밑 열 자리까지 출력합니다. 10^-7 이상의 상대/절대 오차가 허용됩니다.

예제 입력

1
7 14
0 1 1.3
0 2 1.1
0 3 1.24
3 4 1.17
3 5 1.24
3 1 2
1 2 1.31
1 2 1.26
1 4 1.11
1 5 1.37
5 4 1.24
4 6 1.77
5 6 1.11
2 6 1.2

예제 출력

1.3200000000

풀이

다익스트라 최단 경로 알고리즘이라는데, 너비 우선 탐색을 사용하는 알고리즘이다.
BFS를 사용한지 오래되서 익숙해지는데 시간이 좀 걸렸다.

BFS를 잘 쓰는 사람이라면 무난하게 풀 수 있는 문제이지 않을까 한다. ~필자는 아니다.~

너비 우선 탐색을 해 가며, 노이즈가 작은 경로를 최신화 시켜주면 되는 문제이다.

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<vector>
#include<utility>
#include<limits>
#include<queue>

using namespace std;

const double INF = numeric_limits<double>::max();
int N;
vector<pair<int, double>> adj[10000];

double minNoise() {
	vector<double> noise(N, INF);
	noise[0] = 1;

	priority_queue<pair<double, int>> pq;
	pq.push(make_pair(-1, 0));

	while (!pq.empty()) {
		int here = pq.top().second;
		double hereNoise = -pq.top().first;
		pq.pop();

		if (hereNoise > noise[here])
			continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i].first;
			double nextNoise = hereNoise * adj[here][i].second;

			if (noise[next] > nextNoise) {
				noise[next] = nextNoise;
				pq.push(make_pair(-nextNoise, next));
			}
		}
	}

	return noise[N - 1];
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		int M;
		cin >> N >> M;
		//init
		for (int i = 0; i < N; i++) {
			adj[i].clear();
		}

		for (int i = 0; i < M; i++) {
			int a, b;
			double noise;
			cin >> a >> b >> noise;
			adj[a].push_back(make_pair(b, noise));
			adj[b].push_back(make_pair(a, noise));
		}

		cout << fixed;
		cout.precision(10);
		cout << minNoise() << endl;
	}

	return 0;
}

풀이 후기

필자는 방문하는 정점의 노이즈를 꺼내어 곱해주지만, 도서 풀이해서는 노이즈에 log를 취해주어 곱셈연산이 아닌 덧셈연산을 한다. 이 알고리즘이 다익스트라 알고리즘과 좀 더 가까운 것 같다.
하지만 알고리즘 속도가 곱셈을 사용하는 것 보다 약간 느린것으로 보아, log를 취하는 과정에 시간이 좀 걸리는 것 같다.