[ BOJ / C++ ] 1240번 : 노드사이의 거리

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

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

---

[  문제  ]

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

[  입력  ]

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

[  출력  ]

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

[  제한  ]

• $2≤N≤1\,000$ 
• $1≤M≤1\,000$ 
• 트리 상에 연결된 두 점과 거리는 $10\,000$ 이하인 자연수이다.
• 트리 노드의 번호는 $1$부터 $N$까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다.

---

[  문제 접근 및 풀이  ]

트리 상의 두 점의 거리는 1이 아닌 10,000 이하의 자연수이므로

트리를 만들 때 자식의 값과 두 점의 거리 값을 넣어주었고

이후 노드 한 쌍을 입력 받고 한 노드를 루트노드라고 생각 후 큐에 넣어

또 다른 노드와 만났을 때 거리를 출력했다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int N,M;
vector<pair<int,int>> tree[1001];
bool vis[1001];
void Q_1240();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_1240();
}
void Q_1240(){
    cin >> N >> M;
	for (int i=0; i<N-1; i++) {
		int x, y, l;
		cin >> x >> y >> l;
		tree[x].push_back({ y,l });
		tree[y].push_back({x, l});
	}
	for (int i=0;i<M; i++) {
		memset(vis, false, sizeof(vis));
		int x, y;
		cin >> x >> y;
		queue<pair<int, int>> q;
		q.push({ x,0 });
		vis[x] = true;
		while (!q.empty()) {
			auto cur = q.front(); q.pop();
			if (cur.first == y) {
				cout <<cur.second <<"\n";
				break;
			}
			for (auto dir : tree[cur.first]) {
				if (vis[dir.first]) continue;
				int len = cur.second + dir.second;
				vis[dir.first] = true;
				q.push({ dir.first,len });
			}
		}
	}
}

---