[Baekjoon] 백준 2644번: 촌수계산 (c++)

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

2644번: 촌수계산

부모 자식간은 1촌, 형제간엔 2촌인데.... 1촌으로 착각해서.... 좀 헤맸다....ㅎㅎㅠㅠ 그냥 촌수는 노드간의 간선 개수 라고생각하면 됨!

 

DFS를 이용해서, 노드 사이의 간선의 개수를 구하면 된다. 노드 사이 간선을 구하기위해 양방향으로 노드들을 저장했다.

 

1. num에 노드를 양방향으로 저장

2. 촌수를 계산하기 위해 입력받은 a, b를 DFS 실행

3. a가 b(=goal)과 같아지면 result값을 cnt로 저장후 함수 리턴

 

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101

int num[MAX][MAX] = {0,};
bool isVisited[MAX] = {false,};
int cnt = -1;
int result = -1;

void DFS(int x, int goal, int N){
    isVisited[x] = true;
    cnt++;
    if(x == goal) {result = cnt; return; }
    
    for(int i=1;i<=N;i++){
        if(num[x][i] == 1 && !isVisited[i]) DFS(i, goal, N);
        if(result != -1) return;
    }
    cnt--;
}

int main(){
//    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    int N, a, b, m, x, y;
    
    cin >> N;
    cin >> a >> b;
    cin >> m;
    for(int i=0;i<m;i++){
        cin >> x >> y;
        num[x][y] = 1;
        num[y][x] = 1;
    }

    DFS(a, b, N);
    
    cout << result;
    
    return 0;
}