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

문제

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

1240번: 노드사이의 거리

---

문제 요약

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

---

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <cstring>

#define MAX_N 1000

using namespace std;

int n, m;
int start_node, end_node;

bool visited[MAX_N + 1];
vector<tuple<int, int>> edges[MAX_N + 1];

// DFS 진행
void dfs(int x, int dist) {
    visited[x] = true;

    // 찾아야하는 노드에 접근했다면, 거리 출력
    if (x == end_node) {
        cout << dist << "\n";
        return;
    }

    for (int i = 0; i < edges[x].size(); i++) {
        int y, d;
        tie(y, d) = edges[x][i];

        if (visited[y]) continue;

        dfs(y, dist + d);
    }

}

int main() {

    cin >> n >> m;

    // 트리 입력
    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;

        edges[a].push_back({ b, w });
        edges[b].push_back({ a, w });
    }
    
    // 두 노드 사이의 거리 찾기
    for (int i = 0; i < m; i++) {
        cin >> start_node >> end_node;
        
        dfs(start_node, 0);

        memset(visited, false, sizeof(visited));
    }

    return 0;
}

---

코드 설명

트리 정보를 입력 받고, 인접리스트 형태로 저장한다.

 

시작 노드에서부터 도착 노드를 찾을 때까지 각 노드까지의 거리를 계산하며 DFS를 진행한다.

 

도착 노드를 찾았다면, 현재까지의 거리를 출력하고 탐색을 종료한다.