✅ 인접리스트 ✅ BFS ✅ 깊이(depth)를 세가면서 탐색

문제

1. 해결 로직

• 정점의 개수가 최대 n^2인 250,000개로 굉장히 많은 반면 간선의 개수가 m인 10,000개로 적다. 따라서 인접행렬보다는 인접리스트를 사용한다.
• 친구와 친구의 친구까지만 결혼식에 초대하므로 탐색 깊이가 2까지로 정해져 있다. 따라서 DFS보다는 BFS를 사용한다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<int> frd[501];

bool visited[501];
queue<pair<int, int> > que; // <int, int> : <node, depth>

void BFS(){
    que.push({1,0});
    visited[1] = true;

    while(!que.empty()){
        int node = que.front().first;
        int depth = que.front().second;
        que.pop();

        if(depth < 2){ // 깊이가 2 미만일 경우 다음 노드로 이동
            for(int i=1;i<frd[node].size();i++){ // 이어져 있는 모든 노드로 이동해야 함
                int new_node = frd[node][i];
                if(visited[new_node] == true) continue;
                visited[new_node] = true;
                que.push({new_node,depth+1});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for(int i=1;i<=n;i++){
        frd[i].push_back(0);
    }

    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        frd[a].push_back(b);
        frd[b].push_back(a);
    }

    // for(int i=1;i<=m;i++){
    //     cout << i << " : ";
    //     for(int j=1;j<frd[i].size();j++){
    //         cout <<frd[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    BFS();

    int cnt=0;
    for(int i=1;i<=n;i++){
        if(visited[i] == true) cnt++;
    }

    cout << cnt-1; // (상근)본인은 세지 않는다.

    return 0;
}

3. 시간 복잡도

인접리스트를 사용했으므로 시간 복잡도는 정점의 개수 + 간선의 개수
$O(n+m)$

4. Review

• 인접행렬과 인접리스트의 차이를 알고 적용하는 것이 중요했던 문제
• BFS에서 깊이 depth를 세가면서 탐색하는 방법을 알게된 문제
• 정점이 1부터 주어지므로 인접리스트에 넣을때 i-1로 넣어도 되지만 이해하기 편하게 리스트의 맨 앞을 비어두고 (여기에서는 의미 없는 0을 넣어줌) 그 다음부터 정점들을 넣어주었다.