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

1240번 : 노드사이의 거리

---

 

문제)

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

// 1240. 노드사이의 거리
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<vector<pair<int, int>>> vec;
 
void recur(int cur, int prv, int goal, int pay)
{
    // 목표에 도달했을 경우
    if (cur == goal)
    {
        // 목표까지의 거리를 출력한다.
        cout << pay << '\n';
        return;
    }
 
    for (int i = 0; i < vec[cur].size(); i++)
    {
        // 깊이 우선 탐색이 왔던 길로 역류하지 않도록 한다.
        if (vec[cur][i].first == prv) continue;
        recur(vec[cur][i].first, cur, goal, pay + vec[cur][i].second);
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    vec.resize(n + 1, vector<pair<int, int>>());
 
    int a, b, c;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b >> c;
        vec[a].push_back(make_pair(b, c));
        vec[b].push_back(make_pair(a, c));
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        recur(a, 0, b, 0);
    }
 
    return 0;
}
 

---

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

1240번: 노드사이의 거리