백준 s2 5567 결혼식 c++

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

5567번: 결혼식

 

문제

상근이는 친구와 친구의 친구까지 결혼식에 초대하려고 한다.

친구 관계가 그래프 형식으로 주어질 때, 초대하는 사람의 수는?

 

풀이

그래프 탐색으로 거리가 2인 노드들의 개수를 세주면 된다.

다만 주의할 점은 DFS로 풀면 1, 2, 3이 서로 연결되어 있을 때 3이 거리가 2로 취급되므로 틀렸습니다 가 뜰 수 있다.

 

전체 코드

/*boj s2 5567 결혼식*/
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 502
using namespace std;

int N, M;
vector<int> adj[MAXN];
int vis[MAXN];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    int x, y;
    while (M--) {
        cin >> x >> y;

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vis[1] = 1;
    queue<int> Q;
    Q.push(1);
    int answer = 0;
    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        answer++;
        for (int a : adj[cur]) {
            if (vis[a]) continue;

            vis[a] = vis[cur] + 1;
            if (vis[a] >= 4) continue;
            Q.push(a);
        }
    }

    cout << answer - 1 << "\n";
}