[백준] 2644번 촌수계산

문제: 2644번: 촌수계산

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graph;
vector<bool> visits;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n; // 전체 사람의 수
    cin >> n;
    int num1, num2; // 촌수 계산 서로 다른 두 사람 번호
    cin >> num1 >> num2;
    int m; // 부모 자식 간 관계의 개수
    cin >> m;

    graph = vector<vector<int>>(n + 1); // 0번 인덱스는 안 쓸 것..
    visits = vector<bool>(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y; // x는 y의 부모 번호
        cin >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    queue<pair<int, int>> nexts;
    nexts.push({ num1, 0 });
    visits[num1] = true; // 방문 표시
    int ans = -1;
    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front(); nexts.pop();
        if (cur.first == num2) {
            ans = cur.second;
            break;
        }

        for (int next : graph[cur.first]) {
            if (visits[next] == true) continue;

            nexts.push({ next, cur.second + 1 });
            visits[next] = true; // 방문 표시
        }
    }
    cout << ans << "\n";

    return 0;
}