[BOJ] 2644 - 촌수계산 (C++)

문제

촌수계산

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M, A, B, dist = -1;
vector<int> connect[101];
bool visited[101];

void find(int from, int to, int cur){
    if (from == to) {
        dist = cur;
        return;
    }
    
    visited[from] = true;

    for (int i = 0; i < connect[from].size(); i++){
        int next = connect[from][i];
        if (visited[next]) continue;
        find(next, to, cur+1);
    }

}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N;
    cin >> A >> B;
    cin >> M;
    
    int x, y;
    for (int i = 0; i < M; i++) {
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }

    find(A, B, 0);
    cout << dist;
    return 0;
}

접근

부모-자식 관계이기 때문에 트리 관계라고 생각할 수 있다. 또한 이 트리 안에서 특정 노드를 찾기 위해 아래로, 위로 모두 이동할 수 있어야 한다. 따라서 양방향 연결로 저장하였다. 이를 가지고 재귀함수를 통해 촌수 찾을 다른 하나의 번호를 찾아 나섰고 방문 노드를 다시 방문하지 않기 위해 visited 배열을 통해 처리하였다. 따라서 방문 가능한 노드를 모두 방문한 후에도 찾지 못했다면 -1의 값을 출력할 수 있다.