5567번

5567번 - 결혼

그래프 문제, 음의 가중치가 없고, 모든 간선의 가중치가 동일하기 때문에

BFS를 이용해서 문제를 풀 수 있었다.

친구의 친구까지 결혼식에 초대할 수 있으므로, 1번 정점에서 가중치가 2이하인 것들 중, 방문할 수 없는 것들은 제외한

값을 출력하였다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> v(n + 1);
    while (m--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<int> dist(n + 1, -1);
    int start = 1;
 
    queue<int> q;
    q.push(start);
    dist[start] = 0;
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i];
            if (dist[next] == -1)
            {
                dist[next] = dist[now] + 1;
                q.push(next);
            }
        }
    }
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        if (dist[i] <= 2 && dist[i] != -1)
        {
            ans++;
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}