백준 1240번 (노드사이의 거리, C++) [BAEKJOON]

노드사이의 거리

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까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다.

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

2
7

출처

• 빠진 조건을 찾은 사람: hg7258

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

통과된 코드

DFS를 이용하여 탐색

리펙토링하면 메모리와 시간을 더 줄일 수 있음

#include <iostream>
#include <vector>

using namespace std;

constexpr int MAX = 1001;

int N, M, _End;

vector<int> Nodes[MAX];
vector<int> Distances[MAX][MAX];
bool IsVisted[MAX];


void DFS(int _Len, int _CurNode)
{
	if (_End == _CurNode) {
		cout << _Len << '\n';
		return;
	}

	for (int i = 0; i < Nodes[_CurNode].size(); i++)
	{
		int NextNode = Nodes[_CurNode][i];
		if (IsVisted[NextNode]) 
			continue;
		IsVisted[NextNode] = true;
		DFS(_Len + *Distances[_CurNode][NextNode].begin(), NextNode);
		IsVisted[NextNode] = false;
	}

}

int main()
{
	cin >> N >> M;
	int _S, _E, _D;
	for (int i = 0; i < N-1; i++) {
		cin >> _S >> _E >> _D;
		Nodes[_S].push_back(_E);
		Nodes[_E].push_back(_S);
		Distances[_S][_E].push_back(_D);
		Distances[_E][_S].push_back(_D);
	}

	for (int i = 0; i < M; i++) {
		cin >> _S >> _E;
		_End = _E;
		IsVisted[_S] = true;
		DFS(0, _S);
		IsVisted[_S] = false;
	}


	return 0;
}

방문 체크를 빼먹어서 틀렸다.

추가

    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    cin.tie(NULL);
    cout.tie(NULL);

#include <iostream>
#include <vector>

using namespace std;

constexpr int MAX = 1001;

int N, M, _End;

vector<int> Nodes[MAX];
vector<int> Distances[MAX][MAX];
bool IsVisted[MAX];


void DFS(int _Len, int _CurNode)
{
	if (_End == _CurNode) {
		cout << _Len << '\n';
		return;
	}

	for (int i = 0; i < Nodes[_CurNode].size(); i++)
	{
		int NextNode = Nodes[_CurNode][i];
		if (IsVisted[NextNode]) 
			continue;
		IsVisted[NextNode] = true;
		DFS(_Len + *Distances[_CurNode][NextNode].begin(), NextNode);
		IsVisted[NextNode] = false;
	}

}

int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    cin.tie(NULL);
    cout.tie(NULL);
	cin >> N >> M;
	int _S, _E, _D;
	for (int i = 0; i < N-1; i++) {
		cin >> _S >> _E >> _D;
		Nodes[_S].push_back(_E);
		Nodes[_E].push_back(_S);
		Distances[_S][_E].push_back(_D);
		Distances[_E][_S].push_back(_D);
	}

	for (int i = 0; i < M; i++) {
		cin >> _S >> _E;
		_End = _E;
		IsVisted[_S] = true;
		DFS(0, _S);
		IsVisted[_S] = false;
	}


	return 0;
}