백준 5667번: 결혼식 (C++)

링크

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

풀이방법

해당 문제는 BFS를 응용하여 시작 지점부터 거리를 측정하여, 시작 지점인 1로부터 거리가 1. 2인 값들만 찾아내서 개수를 세면 쉽게 풀 수 있는 문제다. 풀이 코드는 아래와 같다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> adj[505];
int vis[505];
int ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    int u, v;

    for (int i = 0; i < m; i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    queue<int> q;
    q.push(1);
    vis[1] = 1; 

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        for (auto nxt : adj[cur])
        {
            if (vis[nxt]) continue;
            q.push(nxt);
            vis[nxt] = vis[cur]+1;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 2 || vis[i] == 3) ans++; // 시작지점 1로부터 거리가 1,2인 값의 개수를 센다.
    }



   cout << ans << '\n';
}