[BOJ/2644번촌수계산] c++ / BFS

문제

주어진 두 사람의 촌수 관계를 계산하는 문제

 

생각

vector로 풀면 되겠다!

 

문제풀이

1.주어진 두 사람의 정보를 s, e 에 저장

2.s를 큐에 푸쉬 ( 이때, 촌수는 0 임 ) + 방문표시

3.vector[s].size 만큼 반복문 돌면서 방문하지 않은 사람이면 큐에 푸쉬 + 방문표시

4.e인 사람이 나오면 cnt 출력

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define X first
#define Y second
int N, M, s, e, x, y, cnt=0;
int vis[101];
vector<int> map[101];
int BFS() {
    queue<pair<int, int>> Q;
    Q.push({s, 0});
    vis[s] = 1;
    while (!Q.empty()) {
        int nx = Q.front().X;
        int cnt = Q.front().Y;
        Q.pop();

        if ( nx == e ) 
            return cnt;

        for ( int i = 0; i < map[nx].size(); i++ ) {
            if ( vis[map[nx][i]] == 1 ) continue;

            Q.push({map[nx][i], cnt+1});
            vis[nx] = 1;
        }
    }
    return -1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    cin >> s >> e;
    cin >> M;
    for ( int i = 0; i < M; i++ ) {
        cin >> x >> y;
        map[x].push_back(y);
        map[y].push_back(x);
    }
    cout << BFS();

}