C++과 친해지기

5/12. 바이러스 (백준 2606번)

 

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

 

//C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<bool> visited;
vector<vector<int>> g;
int n;

int bfs(int start) {
    queue<int> q;
    int cnt = 0;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int nxt: g[cur]) {
            if (!visited[nxt]) {
                q.push(nxt);
                visited[nxt] = true;
                cnt++;
            }
        }
    }

    return cnt;
}

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

    cin >> n;
    visited = vector<bool>(n + 1, false);
    g = vector<vector<int>>(n + 1, vector<int>());

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

    int cnt = bfs(1);

    cout << cnt << '\n';
}

C++로 그래프 탐색 구현 처음 해봤다. (정답)

1차원 벡터를 전역변수로 사용하는 법: 밖에 vector<bool> visited; 까지만 쓰고 main 함수 안에 visited = vector<bool>(n + 1, false); 써주기

2차원 벡터를 전역변수로 사용하는 법: 밖에 vector<vector<int>> g; 쓰고 main 함수 안에 g = vector<vector<int>>(n + 1, vector<int>()); 써주기