[백준] 2644 촌수계산 C++ 풀이

백준 2664 촌수계산 C++ 풀이

문제 링크

 

 

촌수 관계는 트리 형태이지만, 이를 양방향 그래프로 치환하여 dfs로 풀 수 있다.

만약 p와 c가 같다면, 그래프가 연결되어 있는 것이므로, ans 전역변수에  정답을 저장한다.

한번 dfs가 호출될 때 마다 노드 p에 연결된 미리 방문하지 않은 인접한 노드와, cnt를 1증가한 값을 인자로 dfs를 호출한다.

 

ans를 -1로 초기화 해주었기 때문에, 한번도 업데이트가 되지 않은 경우 가족이 아니기 때문에 초기값 -1을 그대로를 출력하게 된다.

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
using namespace std;
vector<int> arr[101];
int memo[101];
int ans = -1;
void dfs(int p, int c, int cnt){
    //cout <<"p "<<p<<" c "<< c<<" cnt: "<<cnt<<endl;
    memo[p] = 1;
    if(c==p){ans = cnt;return cnt;}
    int z = cnt;
    for(int i=0; i<arr[p].size(); i++){
        if(memo[arr[p][i]]==0){
            dfs(arr[p][i],c, cnt+1);
        }
    }
    
    return;
}
 
int main(){
    int n, m;
    int x,y;
    int a,b;
    cin>>n>>x>>y>>m;
    for(int i=0; i<m; i++){
        cin>> a>>b;
        arr[a].push_back(b);
        arr[b].push_back(a);
    }
 
    dfs(x,y,0);
    cout <<ans<<endl;
 
 
}