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

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

문제

---

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

 

입력

---

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

 

출력

---

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

 

제한

---

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

문제 풀이

---

단순 그래프 탐색 문제.

큐를 사용하여 너비 우선 탐색을 진행하거나, 스택을 사용하여 깊이 우선 탐색을 진행하면 된다. 두 노드 사이의 거리가 모두 동일한 1이 아니므로, 그래프의 정보를 저장할 때 <연결된 노드, 두 노드 사이의 거리>를 저장하는 pair<int, int>로 이루어진 벡터 배열을 사용한다.

탐색을 진행할 때에는 스택 혹은 큐에서 top/front의 정보를 가져와 그 노드와 연결되어 있으면서 아직 탐색되지 않은 노드들을 스택이나 큐에 넣는다. 이때 해당 노드까지의 거리는 첫 노드부터 top/front까지의 거리 + 두 노드 사이의 거리이다. 너비 우선 탐색을 진행할 때에는 큐가 선입선출이므로 한 노드를 탐색했다면 pop()하고, 깊이 우선 탐색을 진행할 때에는 후입선출이므로 연결된 노드가 없거나 연결된 노드를 모두 방문했을 때 pop()하면 된다.

두 노드 사이의 거리가 여러 번 입력되므로 탐색을 진행하기 전 혹은 후에 스택이나 큐에 남은 것들을 정보들을 제거하고 방문했는지를 저장하는 배열도 초기화해주어야 한다.

 

 

아래는 dfs로 구현한 코드.

#include <iostream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
stack<pair<int, int>> dfsStack;
vector<pair<int, int>>* graph;
bool* isVisited;
int N, M;

void dfs(int startPos, int endPos)
{
	isVisited[startPos] = true;
	dfsStack.push(pair(startPos, 0));
	while (!dfsStack.empty())
	{
		pair<int, int> current = dfsStack.top();
		bool isAdjacent = false;
		if (current.first == endPos)
		{
			cout << current.second<<"\n";
			break;
		}
		for (int i = 0; i < graph[current.first].size(); i++)
		{
			pair<int, int> next = graph[current.first].at(i);
			if (isVisited[next.first] == false)
			{
				isVisited[next.first] = true;
				dfsStack.push(pair(next.first, current.second + next.second));
				isAdjacent = true;
			}
		}
		if (isAdjacent == false)
		{
			dfsStack.pop();
		}
	}
}

void reset()
{
	for (int i = 0; i < N; i++)
	{
		isVisited[i] = false;
	}
	while (!dfsStack.empty())
	{
		dfsStack.pop();
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int A, B, C;
	cin >> N >> M;
	graph = new vector<pair<int, int>>[N];
	isVisited = new bool[N];
	for (int i = 0; i < N; i++)
	{
		isVisited[i] = false;
	}
	for (int i = 0; i < N-1; i++)
	{
		cin >> A >> B>>C;
		graph[A - 1].push_back(pair(B - 1, C));
		graph[B - 1].push_back(pair(A - 1, C));
	}
	for (int i = 0; i < M; i++)
	{
		cin >> A >> B;
		reset();
		dfs(A - 1, B - 1);
	}
	return 0;
}