[BOJ] #2644 촌수계산

시간 제한	메모리 제한	정답 비율
1 초	128 MB	44.604 %

 

2644번: 촌수계산

전체 사람 수 n, 촌수를 계산해야 하는 서로 다른 사람의 번호 x, y 관계의 수 m 이 주어지면 아래의 m개의 줄에 부모-자식 관계를 나타내는 a,b가 주어진다.

m개의 줄에 해당하는 관계에 따라서 vector 로 2차원 배열을 형성하고 bfs를 활용하여 문제를 해결하였다.

 

메모리	시간
1988 KB	0 ms

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> p;
 
int n, m, x, y;
vector<vector<int>> v;
queue<p> q;
int chk[101];
 
int main() {
    scanf("%d %d %d %d", &n, &x, &y, &m);
    v.resize(n * m);
    for (int i = 0, a, b; i < m; i++) {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    q.push({ x,0 });
    while (!q.empty()) {
        int pnum = q.front().first;
        int pcnt = q.front().second;
        q.pop();
        if (pnum == y) {
            printf("%d", pcnt);
            return 0;
        }
 
        for (auto e : v[pnum]) {
            if (!chk[e]) {
                chk[e] = 1;
                q.push({ e, pcnt + 1 });
            }
        }
    }
    printf("-1");
    return 0;
}