[백준 5567번] 결혼식

문제 링크: https://www.acmicpc.net/problem/5567

5567번: 결혼식

<문제 풀이> 그래프, BFS

자신의 친구와, 친구의 친구까지 초대하는 거니깐 BFS로 자신의 위치인 1번 정점에서 거리가 최대 3까지만 탐색하면 됩니다.

무방향 그래프이므로 인접 리스트를 양방향으로 갱신해줍니다.

 

거리를 체크하는 방법은 큐에 next를 삽입하고 visited배열로 방문 체크할 때 다음과 같이 거리에 대한 정보를 넣어주면 됩니다.

visited[next] = visited[cur] + 1;

<C++ 소스 코드>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n, m;
int visited[501];
vector<vector<int> > adj(501);
int cnt = 0;
 
void bfs() {
    queue<int> q;
    q.push(1);
    visited[1] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& next : adj[cur]) {
            if (visited[next] || visited[cur] >= 3)continue;
            q.push(next);
            visited[next] = visited[cur] + 1;
            cnt++;
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs();
    cout << cnt;
    
 
    return 0;
}