Boj2644

백준 2644

백준 2644번

촌수 계산

DFS로 풀 경우 각 간선의 가중치를 1로 두고, 촌수를 계산해야 하는 사람 중 한 명으로부터 DFS를 시작해 나가면 된다.

하지만 이 경우 두 사람의 친척 관계가 전혀 없는 경우를 처리하기가 번거롭다고 생각해 그냥 BFS로 하였다.

BFS로 구현할 경우 촌수를 계산해야 하는 사람 중 한 명을 루트 노드로 두고 BFS를 진행해 레벨(depth) 를 계산해 출력하면 된다.

만약 queue가 비었다면 두 사람은 같은 그래프에 속하지 않은 것이기 때문에 -1을 출력하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>

using namespace std;
vector<int> arr[101];
bool visited[101]={false,};

int dfs(int n, int sum);
int bfs();
stack<int> s;
int N,start,dst,M;
int main(){
    cin >> N >> start >> dst>>M;

    for(int i=0;i<M;i++){
        int parent,child;
        cin >> parent >> child;
        arr[parent].push_back(child);
        arr[child].push_back(parent);
    }

    
    // dfs(start, 0);
    queue<pair<int,int> > q;
    visited[start] = true;
    q.push(make_pair(start,0));
    int answer = 0;
    while(!q.empty()){
        pair<int,int> cur = q.front();
        q.pop();
        if(cur.first == dst){
            cout << cur.second << endl;
            return 0;
        }
        for(int i = 0; i < arr[cur.first].size();i++){
            if(!visited[arr[cur.first][i]]){
                answer++;
                q.push(make_pair(arr[cur.first][i],cur.second+1));
                visited[arr[cur.first][i]] = true;
            }
        }
    }
    cout << -1 << endl;
    

}

// int dfs(int n, int sum){
//     visited[n] = true;
//     int weight = sum;
//     if(n == dst){
//         cout << weight << endl;
//         return -1;
//     }
//     for(int i=0;i<arr[n].size();i++){
//         if(!visited[arr[n][i]]){
//             s.push(1);
//             visited[arr[n][i]] = true;
//             weight += 1;
//             weight = dfs(arr[n][i],weight);
//         }
//     }
//     if(!s.empty()){
//         s.pop();
//         weight -= 1;
//     }
//     return weight;
// }