[백준/BFS&DFS/C++] 2644번 촌수계산 *

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

DFS 사용

#include <bits/stdc++.h>

using namespace std;

int N, M;
int per_a, per_b;
int p, c;
int cnt = -1;
int sol = -1;
int family[101][101];
int visited[100];

void dfs(int n, int now, int per_b){
    visited[now] = 1;
    cnt++;
    if(now == per_b){
        sol = cnt;
        return;
    }

    for(int i=1; i<=n; i++){
        if(visited[i] == 1) continue;
        if(family[now][i] == 0) continue;
        dfs(n, i, per_b);
    }
    cnt--;
}

void input(){
    cin >> N;
    cin >> per_a >> per_b;
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> p >> c;
        family[p][c] = 1;
        family[c][p] = 1;
    }
}

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

    input();
    dfs(N, per_a, per_b);
    cout << sol;

    return 0;
}

 

BFS 사용

#include <bits/stdc++.h>

using namespace std;

int N, M;
int per_a, per_b;
int p, c;
int cnt = 0;
int family[101][101];
int visited[100];
queue<int> q;

void bfs(int k){
    q.push(k);

    while(!q.empty()){
        k = q.front();
        q.pop();
        for(int i=1; i<=N; i++){
            if(family[k][i]!=0 && !visited[i]){
                q.push(i);
                visited[i] = visited[k] + 1;
            }
        }
    }
}

void input(){
    cin >> N;
    cin >> per_a >> per_b;
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> p >> c;
        family[p][c] = 1;
        family[c][p] = 1;
    }
}

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

    input();
    bfs(per_a);

    if(visited[per_b]==0)
        visited[per_b] = -1;

    cout << visited[per_b];

    return 0;
}