백준 1240번: 노드사이의 거리 (C++)

문제링크

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

풀이방법

해당 문제를 해결한 sequence는 다음과 같다. 기본적으로 bfs를 사용했고 bfs를 통해서 각 노드를 탐색해 나가면서 시작 노드로부터의 거리를 전부 구하면 된다.

• vector<pair<int,int>> adj[1005]; 변수를 통해서 특정 두 노드의 번호와 거리를 입력받는다.
• int bfs(int start, int end) 함수를 통해서 말그대로 start지점을 트리의 루트로 생각하고 탐색을 시작하여 end 지점까지의 거리를 구하기 위해서 dist 배열을 통해서 탐색해나가는 노드와의 거리를 계산해나간다. 최종적으로 dist[end]를 return하여 입력받은 두 노드 사이의 거리를 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;


int n , m , u , v , d;
vector<pair<int, int>> adj[1005];
int dist[1005];


int bfs(int start, int end) {
	// 노드 쌍의 시작점을 트리의 루트로 생각하고 끝점까지 
	// 탐색하면서 루트로 부터의 해당 노드까지의 거리를 dist[노드] 배열에 저장한다.
	fill(dist, dist + 1005, -1);
	queue<int> q;
	q.push(start);
	dist[start] = 0;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (auto nxt : adj[cur])
		{
			if (dist[nxt.first] != -1) continue;
			dist[nxt.first] = dist[cur] + nxt.second; 
			// dist[cur] : start부터 cur까지의 거리
			// nxt.second : cur부터 nxt.fisrt까지의 거리
			q.push(nxt.first);
		}
	}
	return dist[end]; //start부터 end까지의 거리 즉, 정답 출력
}


int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n - 1; i++)
	{
		cin >> u >> v >> d;
		adj[u].push_back({ v,d }); // u노드와 v노드 사이의 거리는 d
		adj[v].push_back({ u,d }); // u노드와 v노드 사이의 거리는 d
	}
	
	while (m--)
	{
		cin >> u >> v;
		cout << bfs(u, v) << '\n';
	}
}