[C++/백준] 1240번: 노드사이의 거리

문제 링크

1240번: 노드사이의 거리

 

풀이

BFS를 이용하는 문제

1. 먼저 노드와 거리를 입력 받아 인접 리스트를 만든다.
2. 거리를 알고 싶은 노드 쌍 stt, end의 입력을 받으면서 BFS함수를 실행한다.
   1. dist 벡터는 stt 노드에서 각 인덱스 노드까지의 거리를 저장하는 벡터로 -1로 초기화한다.
   2. stt 인덱스는 0으로 초기화 한 뒤, queue를 이용해 너비 탐색을 시작한다.
   3. 현재 노드인 cnode와 연결된 노드들을 반복문으로 탐색하며 다음 노드들을 q에 넣고, 거리가 처음 갱신 되는 노드들은 dist[tnode]=dist[cnode]+twei로 갱신한다.
3. dist[end]를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int BFS(int stt, int end, vector<vector<pair<int, int>>> node)
{
    vector<int> dist(node.size(), -1); // stt 노드에서 각 노드까지의 거리 저장
    dist[stt] = 0;
    queue<int> q;
    q.push(stt);

    while (!q.empty())
    {
        int cnode = q.front(); // 현재 노드
        q.pop();
        for (int i = 0; i < node[cnode].size(); i++)
        {
            int tnode = node[cnode][i].first; // 다음 노드
            int twei = node[cnode][i].second; // 다음 노드까지의 거리
            if (dist[tnode] != -1) continue; // 방문했던 노드라면
            dist[tnode] = dist[cnode] + twei; // 다음 노드 거리 갱신
            q.push(tnode);
        }
    }

    return dist[end];
}

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

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> node(n+1);
    for (int i = 0; i < n - 1; i++)
    {
        int stt, end, wei;
        cin >> stt >> end >> wei;
        node[stt].push_back({ end,wei });
        node[end].push_back({ stt,wei });
    }

    for (int i = 0; i < m; i++)
    {
        int stt, end;
        cin >> stt >> end;
        cout << BFS(stt, end, node) << '\n';
    }
}