2644번 촌수계산 | BFS | Baekjoon BOJ 백준 2644 C++ 코드, 해설, 풀이

 

 

 

이번 포스팅은 백준 2644번 촌수계산입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/2644

2644번: 촌수계산

 

 

 

기본 알고리즘

BFS 너비 우선 탐색

 

 

 

전체 코드

 

//백준2644 촌수계산                                                                   
 
#include <iostream>
#include <queue>
using namespace std;
 
const int MAX = 100;
int n;
int a, b;
int map[MAX][MAX] = { 0, };
bool visited[MAX] = { 0, };
int depth[MAX] = { 0, };
queue<int> q;
 
void BFS(int v) {
    q.push(v);
    visited[v] = true;
 
    while (!q.empty()) {
        v = q.front();
        q.pop();
 
        for (int w = 1; w <= n; w++) {
            if (map[v][w] == 1 && visited[w] == 0) {
                q.push(w);
                visited[w] = true;
                depth[w] = depth[v] + 1;
            }
        }
    }
 
}
 
 
int main() {
    cin >> n;
    cin >> a >> b;
 
    int m;
    cin >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        map[x][y] = 1;
        map[y][x] = 1;
    }
 
    BFS(a);
 
    if (depth[b] == 0)
        cout << -1;
    else
        cout << depth[b];
 
}