백준 2644:촌수계산

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

백준 2644번 촌수계산 문제입니다. BFS문제이긴한데.. 어째 제가 푼 방법은 DFS인것 같기도 하고.. 원래 부모부터 계산해야되는거 같긴한데.. 그냥 촌수를 알고싶은 두명 중 한명을 택해서 간선의 갯수? 만큼 카운팅을 해줬습니다. 

밑에는 제 코드입니다.

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<vector<int>> cousin;
vector<int> visited;
 
int n, m; //n:전체 사람 수/m:관계의 개수
 
int cal(int from, int to) {
    queue<int> q; q.push(from); visited[from] = true;
    vector<int> cnt; cnt.resize(n, 0);
    while (!q.empty()) {
        int cur = q.front();
        if (cur == to) return cnt[to];//촌수 계산 가능
        for (int k = 0; k < cousin[cur].size(); k++) {
            int next = cousin[cur][k];
            if (!visited[next]) {//방문하지 않았다면
                cnt[next] = cnt[cur] + 1;//촌수++
                q.push(next);//큐에 삽입
                visited[next] = true;//방문체크
            }
        }
        q.pop();
    }
    return -1;//from에서 to로 갈 
}
 
int main(void) {
    int from, to;
    cin >> n;
    cin >> from >> to;
    cin >> m;
    cousin.resize(n); visited.resize(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        cousin[u - 1].push_back(v - 1);
        cousin[v - 1].push_back(u - 1);
    }
 
    int c = cal(from - 1, to - 1);
 
    cout << c << endl;
 
 
    return 0;
}

modifyed 2018.4.19