[BOJ / C++] 노드사이의 거리 (트리)

문제링크: https://www.acmicpc.net/problem/1240

 

> 방법 1. DFS

1-1. 코드

#include <bits/stdc++.h>
using namespace std;

int dfs(int cur, int dst, vector<vector<pair<int, int>>>& adj, vector<bool>& vis) {
    if (cur == dst) return 0;

    vis[cur] = true;
    for (auto& nx : adj[cur]) {
        int nxt, w;
        tie(nxt, w) = nx;

        if (vis[nxt]) continue;
        
        int res = dfs(nxt, dst, adj, vis);
        
        if (res != -1) return res + w;
    }
    return -1;
}

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

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> adj(n+1);
    for (int i = 0; i < n-1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    while (m--) {
        int u, v;
        cin >> u >> v;
        
        vector<bool> vis(n+1, false);

        cout << dfs(u, v, adj, vis) << '\n';
    }
}

 

 

1-2. 시간복잡도

\(n=1000, m=1000\)이므로 m * DFS 순회를 진행하고 \(O(m(n+n-1)) = 2 \times 10^{6} <10^{8}\)이므로 시간제한 1초 내에 통과 가능하다.

 

1-3. 분석

DFS를 이용해 cur==dst가 될 때까지 찾아 내려간다. 만약 못찾으면 -1을 리턴해서 계속 -1이 리턴되게 하고 찾았을 때는 0을 리턴해서 w를 더하면서 재귀를 복귀해 올라오도록 한다. 이를 BFS로도 구현할 수 있다.

 

 

> 방법 2. BFS (ChatGPT)

2-1. 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int N, M;
vector<vector<pii>> adj;

int bfs(int start, int target) {
    vector<int> visited(N+1, 0);
    queue<pair<int,int>> q; // {node, dist}
    q.push({start, 0});
    visited[start] = 1;

    while(!q.empty()) {
        auto [cur, dist] = q.front(); q.pop();
        if(cur == target) return dist;
        for(auto [nxt, w] : adj[cur]) {
            if(!visited[nxt]) {
                visited[nxt] = 1;
                q.push({nxt, dist + w});
            }
        }
    }
    return -1; // 못 찾는 경우는 없음 (트리니까)
}

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

    cin >> N >> M;
    adj.assign(N+1, {});
    for(int i=0; i<N-1; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    while(M--) {
        int u,v; cin >> u >> v;
        cout << bfs(u,v) << "\n";
    }
}

 

 

2-2. 시간복잡도

DFS와 동일하다.

 

2-3. 분석

BFS를 이용할 때는 옆으로 퍼져나가므로 큐에서 누적된 weight를 들고 이동할 수 있도록 해야한다. 누적된 weight를 들고 다니면서 dst에 도달했을 때 해당 값을 리턴해주면 된다.