[백준] 1240 노드사이의 거리(복습+최적화)

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

 

노드, 즉 정점이 존재하고 노드간 비용이 서로 다른 간선이 존재할 때, 두 노드 사이의 최단거리를 구하려면 다익스트라 알고리즘을 사용해야 합니다. 하지만 이 문제는 그래프가 "트리"의 형태이므로 두 노드 사이의 거리는 유일합니다. 따라서 문제에서도 두 노드 사이의 최단거리가 아닌 그냥 거리를 구하라고 했습니다.

 

따라서 간선간 비용은 다르지만 길이 유일하므로, BFS를 사용하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>tree[1001];
int v[1001];
int bfs(int from, int to) {
	memset(v, -1, sizeof(v));
	v[from] = 0;
	queue<int>q;
	q.push(from);
	while (!q.empty()) {
		auto root = q.front(); q.pop();
		if (root == to)return v[root];
		for (auto [nxt, cost] : tree[root]) {
			if (v[nxt]==-1) {
				v[nxt] = v[root] + cost;
				q.push({ nxt });
			}
		}
	}
}
int main() {
	int n, m, a, b, c;
	cin >> n >> m;
	while (--n) {
		cin >> a >> b >> c;
		tree[a].push_back({ b,c });
		tree[b].push_back({ a,c });
	}
	while (m--) {
		cin >> a >> b;
		cout << bfs(a, b) << "\n";
	}
}

 

아래는 1년전 제출했던 코드입니다.

#include<bits/stdc++.h>
using namespace std;
vector<int>answer;
int visited[1001];
vector<int> st;
int c;
bool flag;
void dfs(int s, int t, vector<vector<int>> &map) {
	st.push_back(s);
	visited[s] = 1;
	for (int i =1;i < map[s].size();i++) {
		if (map[s][i] != -1) {
			if (visited[i])
				continue;
			else if (i == t) {
				st.push_back(t);
				flag = true;
				return;
			}
			else {
				dfs(i, t, map);
				if (flag)
					return;
			}
		}
	}
	if (!st.empty())
		st.pop_back();
	return;
}
int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	int n, m, x, y, a, b,c;
	cin >> n >> m;
	vector<vector<int>>map;
	fill(visited, visited + n + 1, 0);
	for (int i = 0;i <= n;i++) {
		vector<int>vec(n + 1,-1);
		map.push_back(vec);
	}
	for (int i = 0;i < n - 1;i++) {
		cin >> a >> b >> c;
		map[a][b] = c;
		map[b][a] = c;
	}
	for (int i = 0;i < m;i++) {
		cin >> x >> y;
		fill(visited, visited + n + 1, 0);
		c = 0;flag = false;st.clear();
		dfs(x, y, map);
		for (int i = 0;i < st.size()-1;i++) {
			c += map[st[i]][st[i + 1]];
		}
		answer.push_back(c);
 	}
	for (int i = 0;i < answer.size();i++) {
		cout << answer[i] << "\n";
	}
	return 0;
}