[백준][2644번] 촌수계산[cpp, c++]

백준 2644 촌수계산

• 완전 탐색 문제이다.
• https://www.acmicpc.net/problem/2644

• 문제풀이
  1) 주어지는 좌표(촌수)에 대한 그래프를 생성한 후, 시작 좌표(촌수) 끝 좌표(촌수)의 거리를 구하면 되는 문제이기 BFS, DFS 둘 중 하나를 쓰면된다.
  2) 나는 BFS가 더 편하기에 BFS를 사용했다..

 
 
 #include<iostream>
#include<stack>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int a[102][102];
queue<int> q;
int check[102];
int n, s, e, m, x, y;
 
void input_data() {
    cin >> n >> s >> e >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        //그래프 연결
        a[x][y] = 1;
        a[y][x] = 1;
    }
    q.push(s);
    check[s] = 1;
}
 
int bfs() {
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == e) {
            return check[x];
            //찾음;
        }
        for (int i = 1; i <= n; i++) {
            int y = a[x][i];
            if (y == 1 && check[i]==0) {
                // << "y:" << y << " ";
                check[i] = check[x] + 1;
                q.push(i);
            }
        }
    }
    return 0;
}
 
int main(void) {
    input_data();
    int ans = bfs();
    if (ans == 0) cout << -1;
    else cout << ans-1;
 
}