2644 촌수계산

문제 링크

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

풀이

서로 부모-자식 관계라는 것은 노드 사이에 간선이 있다는 것과 마찬가지이므로 친척을 노드, 부모-자식 관계인 경우를 간선으로 생각하여 DFS로 풀었다. 만약 DFS를 통해 원하는 친척까지의 depth를 구할 수 있다면 depth를 출력하고, 구할 수 없다면 -1을 출력한다.

C++ 코드

#include <iostream>

using namespace std;

int n, a, b;
int arr[101][101];
bool visit[101];
int ans = 0;

void dfs(int N, int depth){
    if(N == b) {ans = depth; return;}
    visit[N] = true;
    for(int i=1; i<=n; i++){
        if(arr[N][i] == 1 && !visit[i]){
            dfs(i, depth+1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int m;
    cin>>n>>a>>b>>m;
    
    for(int i=0; i<m; i++){
        int x, y;
        cin>>x>>y;
        arr[x][y] = arr[y][x] = 1;
    }
   
    dfs(a, 0);
    
    if(ans == 0) cout<<-1<<endl;
    else cout<<ans<<endl;
    
    return 0;
}