[BOJ/Gold 5] 백준 1240 노드사이의 거리(C++)

문제 링크

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

1240번: 노드사이의 거리

문제

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

입력

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

출력

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

예제 입력 1

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력 1

2
7

알고리즘 분류

• 그래프 탐색
• 트리

풀이

모든 노드를 다 연결하고 M개의 노드 쌍마다 각각 BFS를 이용해서 이동 거리를 계산하였다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1005
#define LL long long
#define INF 2e9

using namespace std;
int N, M;
vector<pair<int, int> > Vec[MAX];
bool visited[MAX];

void init() {
	for (int i = 0; i < MAX; i++) {
		visited[i] = false;
	}
}

int BFS(int X, int Y) {
	init();
	queue<pair<int, int> > Q;
	visited[X] = true;
	Q.push(make_pair(X, 0));

	while (!Q.empty()) {
		int CurX = Q.front().first;
		int CurCost = Q.front().second;
		Q.pop();

		if (CurX == Y) {
			return CurCost;
		}

		for (int i = 0; i < Vec[CurX].size(); i++) {
			int nextX = Vec[CurX][i].first;
			int nextCost = Vec[CurX][i].second;
			if (!visited[nextX]) {
				visited[nextX] = true;
				Q.push(make_pair(nextX, CurCost + nextCost));
			}
		}
	};
}

int main() {
	FIRST
	cin >> N >> M;
	for (int i = 0; i < (N - 1); i++) {
		int X, Y, D;
		cin >> X >> Y >> D;
		Vec[X].push_back(make_pair(Y, D));
		Vec[Y].push_back(make_pair(X, D));
	}
	for (int i = 0; i < M; i++) {
		int X, Y;
		cin >> X >> Y;
		cout << BFS(X, Y) << "\n";
	}

	return 0;
}