[KOI] 백준 2644 - 촌수계산

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

 

가족 관계는 트리 형태를 가진다. 따라서 어떤 노드 A에서 B가 연결되어 있다면 그것은 단순 경로이다.

 

가족의 관계를 그래프로 구성하고 단순히 BFS를 통해 몇번 거쳐갔는지를 세면 된다.

 

원하는 노드를 찾지 못할 경우 -1을 출력하면 된다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int n;
int mesh[101][101];
bool visited[101];
int a, b;
int e;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> a >> b >> e;

    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < e; ++i)
    {
        int par, chi;
        cin >> par >> chi;
        graph[par].push_back(chi);
        graph[chi].push_back(par);
    }

    queue<pii> q;
    q.push({a, 0});

    while (q.size())
    {
        auto cur = q.front();
        q.pop();
        visited[cur.first] = 1;

        if (cur.first == b)
        {
            cout << cur.second;
            return 0;
        }

        for (int i = 0; i < graph[cur.first].size(); ++i)
        {
            int next = graph[cur.first][i];

            if (!next || visited[next])
                continue;
            
            q.push({next, cur.second + 1});
        }
    }

    cout << -1;
}