[BOJ / C++] 1240 노드사이의 거리

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

 

문제

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

입력

 

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

출력

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

제한

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

---

풀이

트리이므로, 모든 노드는 연결되어 있다.

인근 노드에 대한 정보를 adj에 저장하고, 노드간 거리를 dist에 저장했다.

 

 for (int i = 0; i < n - 1; i++) {
        cin >> from >> to >> d;
        // 인근 노드 정보 저장
        adj[from].push_back(to);
        adj[to].push_back(from);

        // 노드간 거리 저장
        dist[from][to] = dist[to][from] = d;
    }

 

 

이후 dfs를 통해서 노드 from에서부터 to까지 거리를 구한다.

이때 방문 노드가 최종 노드 to일 때, ans를 저장하고 true를 리턴해 탐색을 종료한다.

 

잘못된 경로를 방문할 수 있기 때문에 visited의 상태를 탐색 이후 원복해줘야한다. (백트래킹)

 

bool dfs(int d, int cur, int to) {
    // 거리 찾은 경우 true 리턴
    if (cur == to) {
        ans = d;
        return true;
    }

    // 인근 노드 탐색
    for (auto next : adj[cur]) {
        // 방문한 적 있는 경우 제외
        if (visited[next]) {
            continue;
        }
        visited[next] = 1;

        // 찾은 경우 종료
        if (dfs(d + dist[cur][next], next, to)) {
            return true;
        }
        visited[next] = 0;
    }
    return false;
}

 

전체 코드

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

int n, m, ans = 0;
vector<int> adj[1004];
int visited[1004];
int dist[1004][1004];

bool dfs(int d, int cur, int to) {
    // 거리 찾은 경우 true 리턴
    if (cur == to) {
        ans = d;
        return true;
    }

    // 인근 노드 탐색
    for (auto next : adj[cur]) {
        // 방문한 적 있는 경우 제외
        if (visited[next]) {
            continue;
        }
        visited[next] = 1;

        // 찾은 경우 종료
        if (dfs(d + dist[cur][next], next, to)) {
            return true;
        }
        visited[next] = 0;
    }
    return false;
}

int main() {
    cin >> n >> m;
    int from, to, d;

    for (int i = 0; i < n - 1; i++) {
        cin >> from >> to >> d;
        // 인근 노드 정보 저장
        adj[from].push_back(to);
        adj[to].push_back(from);

        // 노드간 거리 저장
        dist[from][to] = dist[to][from] = d;
    }

    while (m--) {
        cin >> from >> to;
        memset(visited, 0, sizeof(visited));
        ans = 0;
        visited[from] = 1;

        dfs(0, from, to);
        cout << ans << "\n";

        visited[to] = 0;
    }

    return 0;
}