촌수계산 2644

문제

접근 방법

문제 설명에서 나와 있듯 직계자손이 아닌 경우도 있다. 그것이 반복된다면 방향 그래프로는 힘들 것으로 생각해서 무향 그래프로 만들어줬다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, start, end, m;
    cin >> n >> start >> end >> m;
    vector<vector<int>> map(n + 1, vector<int>());
    vector<bool> isVisted(n + 1);
    queue<pair<int, int>> bfs;
    while (m--)
    {
        int p, c;
        cin >> p >> c;
        map[p].push_back(c);
        map[c].push_back(p);
    }
    bfs.push({start, 0});
    isVisted[start] = true;
    while (!bfs.empty())
    {
        auto cur = bfs.front();
        if (end == cur.first)
            break;
        bfs.pop();
        for (int m : map[cur.first])
        {
            if (isVisted[m])
                continue;
            isVisted[m] = true;
            bfs.push({m, cur.second + 1});
        }
    }
    if (!bfs.empty())
        cout << bfs.front().second;
    else
        cout << -1;
    return 0;
}

풀이

양방향으로 이동할 수 있게 해준 다음 그래프를 탐색해주었다. 예측일 뿐이지 실제로 무향 그래프여야 한다는 확신은 없다. 하지만 W의 형태로 주어진다면 방향 그래프로는 힘들 것이기에 양방향으로 이동할 수 있는 형태로 해주었다.