2644번 : 촌수계산 [C++]

문제 링크

성공 여부(걸린 시간): 성공(18분)

아이디어

기본적인 BFS 문제이다.
처음에는 촌수를 형제, 자매는 1촌이라는 오해를 하고 있어서
단방향으로 하고 부모 자식을 추가할때마다 갱신을 해줘야하나 싶었지만

 

형제, 자매는 2촌이었다.

 

그래서 그냥 양방향으로 연결하고 BFS를 통해서 관계를 구해야 하는 두 노드의 촌수를 계산하면 끝이다.
조심할 것은 방문처리와 촌수를 상태로 저장해서 큐에 넣어줘야하고 큐에 넣을때는 현재까지의 촌수 + 1이다.

풀이 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    int start, end;
    cin >> start >> end;
    int M;
    cin >> M;

    vector<vector<int>> graph(N+1, vector<int>());
    vector<int> visited(N+1, false);

    for (int i = 0; i < M; i++) {
        int parent, child;
        cin >> parent >> child;
        graph[parent].push_back(child);
        graph[child].push_back(parent);
    }

    queue<pair<int, int>> q;
    q.push({start, 0});

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        if (cur.first == end) {
            cout << cur.second;
            return 0;
        }
        for (int x: graph[cur.first]) {
            if(!visited[x]) {
                q.push({x, cur.second+1});
                visited[x]=true;
            }
        }
    }
    cout << -1;

    return 0;
}