BOJ 1240번: 노드사이의 거리

문제 설명

두 노드가 주어졌을 때 두 노드 사이의 거리 구하기

🔗 문제 링크

핵심 아이디어

• DFS를 매 입력마다 돌려서 거리 누적하기
• pair를 이용해서 {연결된 노드, 거리}를 저장
• vis 배열을 이용해서 이미 방문한 노드인지 확인
• 현재 노드가 목적지 노드이면 멈추고 거리 리턴하기

코드

#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, d;
vector<pair<int,int>> adj[1005];
bool vis[1005];

int dfs(int st, int des, int dis){
    vis[st] = true;
    if (st == des) return dis;
    
    for(auto nxt : adj[st]){
        if (vis[nxt.first]) continue;
        int result = dfs(nxt.first, des, dis + nxt.second);
        if (result != -1) return result;
    } 
    
    return -1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < n-1; i++){
        cin >> u >> v >> d;
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        fill(vis,vis+1005,false);
        cout << dfs(u,v,0) << '\n';
    }
}

‼️ 놓친 부분

return -1;

• DFS에서 이 부분 안해주면 런타임 에러 (Without Returning)이 남!
• 이 부분이 출력 안되더라도 코드 구조상 필요함

✨ BFS 버전 코드

// Authored by : heheHwang
// Co-authored by : -
// http://boj.kr/dc926ebf7eb54c308dea376b240e0591

while (M--) {
    cin >> u >> v;
    queue<pair<int, int>> q;
    vector<bool> vis(N + 1);
    q.push({u, 0});
    vis[u] = true;
    while (!q.empty()) {
      auto [cur, dist] = q.front();
      q.pop();
      if (cur == v) {
        cout << dist << '\n';
        break;
      }
      for (auto [nxt, nxtDist] : adj[cur]) {
        if (vis[nxt]) continue;
        vis[nxt] = true;
        q.push({nxt, dist + nxtDist});
      }
    }

• DFS 말고 BFS로도 이렇게 구현 가능!