[BOJ] 1240 : 노드사이의 거리

1240 : 노드사이의 거리

문제

문제

$N$개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

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

출력

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

풀이

그래프와 너비우선탐색을 활용하면 풀 수 있는 문제다.

N-1 개의 간선 정보를 저장한 뒤,
출발점과 도착점을 알기 위해 너비우선탐색을 수행한다.

dist 벡터는 출발점 u 와 해당 노드의 거리를 나타내기 때문에,
새로운 질문을 받을 때마다 초기화해주어야 한다.

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

using namespace std;

int n, m;
vector<pair<int, int>> adj[1001];
vector<int> dist(1001);

int bfs(int u, int v)
{
	queue<int> q;

	q.push(u);

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		for (auto next : adj[cur])
		{
			if (dist[next.first] > 0) continue;
			dist[next.first] = dist[cur] + next.second;
			q.push(next.first);
		}
	}

	return dist[v];
}

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

	cin >> n >> m;


	for (int i = 0; i < n - 1; ++i)
	{
		int u, v, e;
		cin >> u >> v >> e;

		adj[u].push_back({ v,e });
		adj[v].push_back({ u,e });
	}

	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;

		fill(dist.begin(), dist.end(), 0);

		cout << bfs(u, v) << '\n';
	}

	return 0;
}