백준 1240 : 노드사이의 거리

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

1240번: 노드사이의 거리

 

문제에서 주어지는 엣지들로 이루어진 트리에서 두 노드 사이의 거리를 구하는 문제이다.

나는 이런 문제를 볼 때마다 트리를 어떻게 구성해야 하나 헷갈리는데 이런 경우 루트 노드를 어떤 노드로 잡던지 트리를 형성할 수 있고, 구하는 값에 변화가 없다.

 

이 문제는 간선에 가중치가 있는 트리 문제로, BFS, 다익스트라 두 가지 방법으로 풀어보았다.

 

풀고나서 생각해보니 트리 구조에서 노드 a에서 노드 b로 이동하는 경로는 무조건 하나이므로 다익스트라는 적절하지 않다.

다익스트라 같은 경우 그래프 알고리즘으로, 노드 a에서 노드 b로 가는 경로가 여러개 일 경우 경로를 더 짧은 경로로 갱신 시키는 로직인데, 트리의 경우 경로가 하나이기 때문에 의미없는 연산을 반복하게 되어 비효율적이다.

 

1. BFS 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

#define DIST first
#define POS second

using namespace std;
using pii = pair<int, int>;

int n, m;
vector<pii> edge[1001];
bool visited[1001];

void input() {
	int node1, node2, dist;
	cin >> n >> m;

	for (int i = 0; i < n - 1; i++) {
		cin >> node1 >> node2 >> dist;
        //양방향 간선이므로
		edge[node1].emplace_back(dist, node2);
		edge[node2].emplace_back(dist, node1);
	}
}

int bfs(int from, int to) {
	int cur, cur_dist, npos, n_dist;
	queue<pii> q;
	q.emplace(0, from);
	visited[from] = 1;

	while (!q.empty()) {
		cur = q.front().POS;
		cur_dist = q.front().DIST;
		q.pop();
		
        //트리이므로 처음 도착했을 때가 유일한 경로이고 최단거리임
		if (cur == to) break;

		for (int i = 0; i < edge[cur].size(); i++) {
			npos = edge[cur][i].POS;

			if (visited[npos]) continue;

			n_dist = cur_dist + edge[cur][i].DIST;
			q.emplace(n_dist, npos);
			visited[npos] = 1;
		}
	}
	return cur_dist;
}

void solution() {
	int from, to;

	input();
	
	while (m--) {
		cin >> from >> to;
		cout << bfs(from, to) << '\n';
		memset(visited, 0, sizeof(visited));
	}
}

int main() {
	ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	solution();

	return 0;
}

메모리: 2180 kb

시간: 8 kb

 

2. 다익스트라 풀이

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define POS second
#define DIST first

using namespace std;
using pii = pair<int, int>;

int n, m;
vector<pii> edge[1001];
int dist[1001];

void input() {
	int node1, node2, dist;
	cin >> n >> m;

	for (int i = 0; i < n - 1; i++) {
		cin >> node1 >> node2 >> dist;
		edge[node1].emplace_back(dist, node2);
		edge[node2].emplace_back(dist, node1);
	}
}

void dijkstra(int from) {
	int cur_pos, cur_dist, n_pos, n_dist;
	priority_queue<pii> pq;
	pq.emplace(0, from);
	dist[from] = 0;

	while (!pq.empty()) {
		cur_pos = pq.top().POS;
		cur_dist = -pq.top().DIST;
		pq.pop();

		if (dist[cur_pos] < cur_dist) continue;
		for (int i = 0; i < edge[cur_pos].size(); i++) {
			n_pos = edge[cur_pos][i].POS;
			n_dist = cur_dist + edge[cur_pos][i].DIST;

			if (dist[n_pos] > n_dist) {
				dist[n_pos] = n_dist;
				pq.emplace(-n_dist, n_pos);
			}
		}
	}
}

void solution() {
	int from, to;

	input();
	
	while (m--) {
		cin >> from >> to;
		fill(dist + 1, dist + n + 1, 1e9);
		dijkstra(from);
		cout << dist[to] << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	solution();

	return 0;
}

메모리: 2184 kb

시간: 72 ms

 

필요하지 않은 노드까지의 거리 정보도 갱신 + 불필요한 거리 비교 연산으로 인하여 BFS보다 상당히 느리다.

그래프와 트리에 대하여 조금 더 잘 알고있었다면 다익스트라를 쓰지 않았을 것이다.

오늘도 CS를 공부해야 하는 이유를 배우고 간다.