[BOJ/C++] 9372 상근이의 여행

시간 복잡도

• BFS를 인접 리스트를 이용해 구현하면 시간 복잡도는 $O(V+E)$ 입니다.

문제 접근법

• 모든 국가를 방문해야 하기 때문에 BFS를 이용하여 모든 노드를 방문한 숫자를 카운트하여 문제를 해결할 수 있습니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>


using namespace std;

using int32 = long;
using int64 = long long;

static vector<vector<int>> G;
static vector<int> visited;

int BFS(int node);

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

    
    int T;
    cin >> T;

    for(int i=0; i<T; i++)
    {
        int N, M;
        cin >> N >> M;

        G = vector<vector<int>>(N + 1);
        visited = vector<int>(N + 1);

        for(int j=0; j<M; j++)
        {
            int s, e;
            cin >> s >> e;

            G[s].push_back(e);
            G[e].push_back(s);
        }

        cout << BFS(1) << '\n';
        
    }


    return 0;
}

int BFS(int node)
{
    int count = 0;
    visited[node] = true;
    queue<int> q;

    q.push(node);

    while(!q.empty())
    {
        int now = q.front();
        q.pop();

        for(int next : G[now])
        {
            if(!visited[next])
            {
                visited[next] = true;
                q.push(next);
                count++;
            }
        }
    }
    return count;
}