[BOJ알고리즘, C++]#1240_노드 사이의 거리, 최단 경로 알고리즘, BFS

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. BFS

[자료구조]#6_그래프

BFS는 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. BFS는 현재 레벨의 가장 인접한 정점들을 우선적으로 탐색합니다. 일반적으로, BFS는 큐 자료구조를 활용합니다.

 

2. BFS = 탐색 or 최단 경로(가중치가 모두 동일한 환경에서만!)

1. 먼저, 트리 자료구조는 그래프의 한 종류입니다. 따라서, DFS 혹은 BFS를 트리 자료구조에서도 역시 활용 가능합니다. 특히, BFS는 가중치가 없는 혹은 동일한 그래프 내 최단 경로(거리)를 찾기 위해 활용됩니다!
2. 해당 문제는 두 노드 사이의 '최단 거리'라고 명시하지 않았기 때문에, 단순히 두 노드 사이의 거리를 찾기 위해 LCA를 활용하기보단, 'BFS'를 활용했습니다!
3. 주어진 출발 노드와 도착 노드를 통해 BFS를 수행하고, 두 노드 사이의 거리를 출력합니다.

 

---

 

#3. 코드

 

/*
    @문제 : 트리의 두 정점 사이의 거리를 구하는 문제
    @설명
            1. 최단 거리가 아니므로, 가중치가 같을 경우 최단 경로를 찾는 BFS활용 최단 경로 알고리즘 구현 
*/

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

#define MAX 1001

int N, M;
int tree[MAX][MAX];

void bfs(int start, int end)
{
    queue<int> q;
    vector<int> parent(N+1, -1);
    vector<bool> visited(N+1, false);
    int res = 0;

    q.push(start);
    visited[start] = true;

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

        if(cur == end)
        {
            while(cur != start)
            {
                res += tree[cur][parent[cur]];
                cur = parent[cur];
            }
            cout << res << '\n';
            return;
        }

        for(int neighbor=1; neighbor<=N; ++neighbor)
        {
            if(!visited[neighbor] && tree[cur][neighbor] != 0)
            {
                visited[neighbor] = true;
                parent[neighbor] = cur;
                q.push(neighbor);
            }
        }
    }

}

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

    cin >> N >> M;

    for(int i=0; i<N-1; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;

        tree[u][v] = w;
        tree[v][u] = w;
    }

    // BFS?
    while(M--)
    {
        int u, v;

        cin >> u >> v;

        bfs(u, v);
    }

    return 0;
}

 

---