백준5567_결혼식_bfs

-문제-

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

 

 

 

-문제 접근-

위 문제는 친구의 친구일 경우까지만 친구로 카운트를 한다고 되어있다. 그 말은 즉 시작점으로 부터 depth가 2까지만 친구로써 카운트 하겠다는 뜻이다. 그렇다면 이 depth를 2까지 어떻게 구별하고 카운트를 할것인가? 를 우리는 생각해야된다.

 

위 문제에서 main은 딱히 다른 bfs의 문제들과 별 차이점이 없이 구성하면 될 거 같다.

 

그렇다면 bfs를 건들여야 하는데 일반적인 bfs는 queue를 하나로 둔다.

하지만 이 문제에서는 queue를 pair로 둬서 노드, dapth 이렇게 두 개를 처리해야 함을 알 수 있다.

그렇게 하면 dapth가 2 이상 일 때는 넘기고 그 전까지의 count를 해주면 문제가 요구하는 답을 구할 수 있다.

 

 queue<pair<int,int>> q; 큐를 쌍으로 선언

int cur = q.front().first;     노드
int depth = q.front().second;   깊이 레벨

 

 

-코드-

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int bfs(const vector<vector<int>>& adj, vector<bool>& vis,int s){
    queue<pair<int,int>> q; //pair로 선언
    vis[s] = true;
    q.push({s,0}); // 노드, 깊이
    int count = 0;
    
    while(!q.empty()){
        int cur = q.front().first;
        int depth = q.front().second;
        
        q.pop();
        if(depth >= 2) continue;
        
        for(int nxt : adj[cur]){
            if(!vis[nxt]){
                vis[nxt] = true;
                q.push({nxt, depth + 1});
                count++;
            }
        }
    }
    return count;
}


int main(){
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> adj(n+1);
    vector<bool> vis(n+1, false);
    
    while(m--){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); //양방향
        adj[v].push_back(u);
        
    }
     
    
    cout << bfs(adj,vis,1);
}