(C++) - 백준(BOJ) 1240번 : 노드사이의 거리

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

1240번: 노드사이의 거리

bfs로 푼 문제였습니다.

 

 

 

📕 풀이방법

📔 입력 및 초기화

 인접리스트로 트리를 구현합니다.

 

 

📔 풀이과정

플로이드 와샬은 1000^3의 시간복잡도가 걸리므로 시간초과가 될 수 있습니다. 따라서 매 출발과 도착점을 입력받을 때마다 출발점을 기준으로 거리를 구해줍니다.

 

 1. 출발점과 도착점의 입력 후에 해당 부분으로 bfs를 수행합니다. 

 

 2. 트리에는 사이클이 없으므로 방문하지 않은 정점까지의 거리는 인접정점에서 그 정점으로 가는 거리를 더한 값이 됩니다.

 

 3. 마지막점의 거리를 구한고 bfs를 종료합니다.

 

📔 정답출력

 bfs수행 결과값을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
struct Node {int v, cost; };
int n, m, dist[1001];
vector <Node> graph[1001];

int bfs(int start, int end){
    queue <int> q;
    q.push(start);
    dist[start] = 0;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto next : graph[x]){
            if(dist[next.v] >= 0) continue;
            dist[next.v] = dist[x] + next.cost;
            q.push(next.v);
        }
    }
    return dist[end];
}

int main(){
    cin >> n >> m;
    for(int i = 0, u,v, cost; i < n - 1; i++){
        cin >> u >> v >> cost;
        graph[u].push_back({v,cost});
        graph[v].push_back({u,cost});
    }
    

    while(m--){
        int start, end;
        cin >> start >> end;
        memset(dist,-1,sizeof(dist));
        cout << bfs(start, end) << '\n';
    }
}