C++ 백준 1240 노드사이의 거리

백준 1240

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

1240번: 노드사이의 거리

풀이 전 나의 생각

N개의 노드로 이루어진 트리와 M개의 두 노드 쌍을 입력 받을 때 

두 노드 사이의 거리를 구해내야 한다.

 

조건

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

과정

조건을 통해 알 수 있는 것은 int 데이터 타입으로 모두 해결 가능하고

트리의 두 노드는 중복된 값의 입력이 불가능하다는 것이다.

 

문제의 포인트는 노드에서 다음 노드로 이동할 때 마다
거리의 누적합을 구해줘야 한다.

 

이를 위해선 추가적으로 거리값을 저장 할 공간을 하나 더 만들어줘야 한다.

 

다음으로 현재 노드에서 다음 노드로 갈 때 마다 필요한 거리의 값과
다음 노드의 정보를 BFS로 탐색하며 구해주면 된다.

 

1. 주어진 노드의 정보와 거리를 저장한다.

for (int i = 0; i < N - 1; i++)
	{
		int f, s, d;
		cin >> f >> s >> d;
		node[f].push_back(make_pair(s, d));
		node[s].push_back(make_pair(f, d));
	}

문제에선 단순한 트리 구조의 탐색이 아닌, 트리구조 탐색 + 거리 계산을 요구하기 때문에
거리의 값을 추가적으로 저장해준다.

 

2. BFS로 트리의 노드를 탐색하며 거리의 누적합을 구한다.

int bfs(int f, int s)
{
	fill(visited, visited + 1005, false);
	queue<pair<int, int>> q;
	visited[f] = true;
	q.push(make_pair(f, 0));

	while (!q.empty())
	{
		int cur_f = q.front().first;
		int cur_d = q.front().second;
		q.pop();

		if (cur_f == s) return cur_d;

		for (int i = 0; i < node[cur_f].size(); i++)
		{
			int nex_f = node[cur_f][i].first;
			int nex_d = node[cur_f][i].second;

			if (!visited[nex_f])
			{
				visited[nex_f] = true;
				q.push(make_pair(nex_f, nex_d + cur_d));
			}
		}
	}
}

BFS에 대한 지식이 있다면 어렵지 않게 풀 수 있다.

만약 BFS와 DFS 또는 재귀에 대한 개념이 부족하다면 먼저 이 부분을 학습하고 
트리의 문제를 푸는 것이 효율적이다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<pair<int, int>>> node(1005);
bool visited[1005];

int bfs(int f, int s)
{
	fill(visited, visited + 1005, false);
	queue<pair<int, int>> q;
	visited[f] = true;
	q.push(make_pair(f, 0));

	while (!q.empty())
	{
		int cur_f = q.front().first;
		int cur_d = q.front().second;
		q.pop();

		if (cur_f == s) return cur_d;

		for (int i = 0; i < node[cur_f].size(); i++)
		{
			int nex_f = node[cur_f][i].first;
			int nex_d = node[cur_f][i].second;

			if (!visited[nex_f])
			{
				visited[nex_f] = true;
				q.push(make_pair(nex_f, nex_d + cur_d));
			}
		}
	}
}

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

	cin >> N >> M;

	for (int i = 0; i < N - 1; i++)
	{
		int f, s, d;
		cin >> f >> s >> d;
		node[f].push_back(make_pair(s, d));
		node[s].push_back(make_pair(f, d));
	}

	for (int i = 0; i < M; i++)
	{
		int f, s;
		cin >> f >> s;

		cout << bfs(f, s) << '\n';
	}
}