[백준] 2606번 바이러스

문제: 2606번: 바이러스

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>

using namespace std;

vector<vector<int>> computers(105);
vector<bool> visit(105);

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n; // 컴퓨터 수
    int m; // 연결된 쌍의 수
    cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        computers[u].push_back(v);
        computers[v].push_back(u);
    }
    // 1번이 웜 바이러스에 걸렸을 때 웜 바이러스에 걸리게 되는 컴퓨터의 수는?
    queue<int> que;
    que.push(1);
    visit[1] = true; // 방문ㅊ처리!
    int ans = 0;
    while (!que.empty()) {
        int cur = que.front();
        que.pop();

        if (cur != 1) {
            ans++;
        }

        for (int next : computers[cur]) {
            if (visit[next]) continue;

            que.push(next);
            visit[next] = 1;
        }
    }
    cout << ans;

    return 0;
}

 

그냥 전형적인 BFS 그래프 문제였다.. 

 

문제에서 1번부터 시작하라고 줬으니까 맨 처음에 que 에 1을 집어넣고 계속 BFS 를 돌렸다. 1이 아닌 next 에 도달했을 때 ans 값을 +1 해주면 된다.