백준 BaekJoon(촌수 계산, 2644번) C++

 

촌수 계산을 Node 간의 거리로 알고리즘을 구성했는데 왜 성공인지...? 아 방금 촌수 계산하는 법을 구글링하고 왔는데 이게 맞다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 각 Node에서 얼마나 떨어져 있는지를 계산하면 촌수를 구할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int size = 0 ,me = 0, you = 0, num = 0;
    cin >> size;
    cin >> me >> you;
    cin >> num;

    vector<vector<int>> arr(size+1);
    vector<int> visited(size+1, 0);

    for(int i = 0 ; i < num ; i++) {
        int one = 0, two = 0;
        cin >> one >> two;
        arr[one].push_back(two);
        arr[two].push_back(one);
    }

    queue<int> q;

    q.push(me);
    visited[me] = 1;

    while(!q.empty()) {
        int node = q.front();
        q.pop();

        for(int j = 0 ; j < arr[node].size() ; j++) {
            if(visited[arr[node][j]] == 0) {
                visited[arr[node][j]] = visited[node] + 1;
                q.push(arr[node][j]);
            }
        }
    }
    // for(int i = 1 ; i <= num ; i++) {
    //     cout << "[" << i << "] ";
    //     for(int j = 0 ; j < arr[i].size() ; j++) {
    //         cout << arr[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    if(visited[you] == 0)
        cout << "-1";
    else
        cout << visited[you] - 1;

    return 0;
}