백준 2644번 - 촌수계산

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

문제를 보면서 풀이 방법에 대해서 정말 많은 고민을 했다.
구해야 하는 두 사람의 촌수를 계산할 때 부모와 자식 관계를 따로 저장해야 하는지...


그런데 생각을 해보니깐 두 사람의 촌수를 계산하려면 부모이든 자식이든 얼마나 떨어져 있는지를 알기만 하면 된다.

예를 들어 1의 자식이 2이고, 2의 자식이 3이라고 해보자.


이때 1과 3의 거리는  1->2->3으로 접근을 해서 3을 구할 수 있다.
그렇다면 그 반대도 가능하다. 3->2->1로 접근을 해서 3을 구할 수 있다.



양방향으로 서로가 연결되어 있도록 저장을 한 다음에
bfs를 통해서 거리 값을 구하면 된다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main() {
 
    int n, p1, p2, m;
    cin >> n >> p1 >> p2 >> m;
 
    int x, y;
    vector<int> vec[101];
    vector<int> visited(101, 0);
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
 
    queue<int> q;
    q.push(p1);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
 
        if (p == p2) {
            break;
        }
 
        for (int i = 0; i < vec[p].size(); i++) {
            if (!visited[vec[p][i]]) {
                visited[vec[p][i]] = visited[p] + 1;
                q.push(vec[p][i]);
            }
        }
    }
 
    if (visited[p2] != 0)
        cout << visited[p2] << endl;
    else
        cout << -1 << endl;
}