촌수계산

코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#define INF 1e9
using namespace std; 
// 12:42 ~ 12:55
int N, A, B, M;
bool vis[101];
int ans = INF;
vector<int> v[101];
void DFS(int n, int cnt){
    if(n == B)
        ans = min(ans, cnt);
    for(int idx=0;idx<v[n].size();idx++)
    {
        if(vis[v[n][idx]]) continue;
        vis[v[n][idx]] = true;
        DFS(v[n][idx], cnt+1);
        vis[v[n][idx]] = false;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> A >> B;
    cin >> M;
    for(int i=0;i<M;i++)
    {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a); // 양방향이기 때문
    }
    vis[A] = true;
    DFS(A, 0);
    if(ans != INF) cout << ans;
    else cout << -1;
    return 0;
}