문제 출처

1. 문제설명

  • 노드와 간선, 노드 간 이동 비용이 주어진다.
  • 두 개의 노드가 주어질 때 이동 비용을 구하라
  • 문제 분류
    • Graph, Tree, BFS, DFS


2. 알고리즘 설계

  • 처음엔 다익스트라로 생각해서 우선순위 큐로 구현하려고 했다.
  • 생각해보니 트리는 노드 간 간선이 하나기 때문에 그럴 필요가 없었다.
  • 로직
    • 주어진 트리를 인접 행렬에 저장한다.
    • 입력으로 주어진 두 개의 노드 중 첫 번째를 src, 두 번째를 dest로 두고 BFS
    • BFS
      • 현재 노드와 비용을 큐에서 꺼낸다.
      • 현재 노드에 인접한 노드를 꺼내서 비용을 갱신한다.


3. 전체 코드

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

const int SZ = 1'005;
int n, m, u, v, d;
vector<pii> adj[SZ];
bool vis[SZ];

int bfs(int src, int dest) {
    queue<pii> q;
    q.push({src, 0});
    vis[src] = true;

    while(!q.empty()) {
        pii cur = q.front();
        q.pop();

        if(cur.first == dest) return cur.second;

        for(pii tmp : adj[cur.first]) {
            int nxt = tmp.first;
            int d = tmp.second;

            if(vis[nxt]) continue;

            q.push({nxt, cur.second+d});
            vis[nxt] = true;
        }
    }

    return -1;
}

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

    cin >> n >> m;
    while(--n) {
        cin >> u >> v >> d;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }

    while(m--) {
        cin >> u >> v;
        cout << bfs(u, v) << '\n';
        fill(vis, vis+SZ, false);
    }

    return 0;
}