백준 2644번 촌수계산 - C++(cpp) 풀이

---

 

1. 각 사람을 정점, 부모 자식 관계를 간선으로 연결하면 결과는 트리를 이룬다.
2. 촌수는 트리에서 두 정점 간의 거리와 같다.
3. DFS나 BFS로 두 정점간의 거리를 구한다.

 

1. 각 사람을 정점, 부모 자식 관계를 간선으로 연결하면 결과는 트리를 이룬다.

 부모 자식 관계에서 사이클이 생성되는 것은 불가능하다. 따라서 결과는 항상 트리 구조이다.

 

2. 촌수는 트리에서 두 정점 간의 거리와 같다.

 촌수는 트리에서 두 정점 사이의 간선의 개수, 즉 두 정점간의 거리를 뜻한다.

 

3. DFS나 BFS로 두 정점간의 거리를 구한다.

 DFS나 BFS로 두 정점 간의 거리를 구하면 된다. 이때 트리에서 두 정점이 연결되어있지 않으면 촌수를 계산할 수 없는 경우이다.

반응형

---

#include <iostream>
#include <vector>

using namespace std;

int N, M, A, B;
vector<int> adj[101];
int depth[101];
bool visit[101];

void DFS(int curr, int d) {
    visit[curr] = true;
    depth[curr] = d;
    
    for (int next : adj[curr]) {
        if (!visit[next]) DFS(next, d+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    cin >> A >> B;
    cin >> M;
    
    int x, y;
    for (int i=0; i<M; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    DFS(A, 1);
    
    cout << depth[B] - 1;

    return 0;
}