노드사이의 거리 1240

문제

접근 방법

트리를 탐색하며 해당하는 위치를 찾으면 된다. 탐색하는 과정에서 방문하는 곳에 거리의 값을 합해가면 두 노드 사이의 거리를 찾을 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
vector<vector<pii>> adj;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, start, end, cost;
    cin >> N >> M;
    vector<vector<pii>> adj(N + 1, vector<pii>());
    vector<bool> visted(N + 1);
    for (int i = 1; i < N; ++i)
    {
        cin >> start >> end >> cost;
        adj[start].push_back({end, cost});
        adj[end].push_back({start, cost});
    }
    for (int i = 0; i < M; ++i)
    {
        cin >> start >> end;
        queue<pii> q;
        fill(visted.begin(), visted.end(), false);
        q.push({start, 0});
        while (!q.empty())
        {
            pii cur = q.front();
            q.pop();
            if (cur.first == end)
            {
                cout << cur.second << "\n";
                break;
            }
            for (pii next : adj[cur.first])
            {
                if (visted[next.first])
                    continue;
                visted[next.first] = true;
                q.push({next.first, cur.second + next.second});
            }
        }
    }
    return 0;
}

풀이

처음에는 플로이드 워셜로 풀려 했다. 풀리긴 하였지만 최대 1,000^3만큼의 작업을 하기에 실행 시간이 꽤 걸렸다.

BFS를 활용하여 요청받을 때마다 탐색한다고 최악의 경우 1000번의 요청에서 모든 노드(1,000)를 탐색한다 해도 1000^2이기에 더 짧은 시간이 나온다.

닭 잡는 데 소 잡는 칼 쓴다는 게 이럴 때를 말하는 것 같다.
때에 따라 방법을 달리해야 함을 느끼게 해주었다.