백준 2644번 촌수

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

풀이

입력으로 전달받은 x, y 의 촌수를 구하는 것은 바꾸어말하면 x, y 사이의 간선의 갯수를 구하면 된다.

이를 depth 라고 표현하였으며 풀이 방법은 아래와 같다.

1. 입력으로 전달받은 각 부모, 자식들을 인접리스트로 구성한다.

2. 방문을 시작하기 전에 x를 queue 에 삽입한 뒤, bfs 로 각 node 를 방문한다.

3. 현재 방문한 사람(cur)의 인접한 사람(node)들의 depth 를 저장한다.

   현재 방문한 사람의 depth + 1 이 인접한 사람의 depth 가 된다.

4. 마지막으로 y 의 값을 출력한다.

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define MAX 100
using namespace std;
bool visit[MAX + 2] = {false, };
int depth[MAX + 2] = {0, };
int main()
{
    queue<int> q;
    int n, m, from, to, parent, child, start;
    bool find = false;
    
    scanf("%d", &n);
    vector<int>v [n+2];
    for (int i = 1; i <= n; ++i) {
        depth[i] = -1;
    }
    
    scanf("%d %d", &from, &to);
    scanf("%d", &m);
    for (int i = 1 ; i <= m; ++i) {
        scanf("%d %d", &parent, &child);
        v[parent].push_back(child);
        v[child].push_back(parent);
    }
    
    q.push(from);
    depth[from] = 0;
    visit[from] = true;
    
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        
        int len = v[cur].size();
        for (int i = 0 ; i < len; ++i) {
            int node = v[cur][i];
            if (!visit[node]) {
                visit[node] = true;
                q.push(node);
                depth[node] = depth[cur] + 1;
            }
        }
    }
    
    printf("%d\n", depth[to]);
    return 0;
}