백준 2606 - 바이러스 [C++]

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

2606번: 바이러스

---

풀이 과정

컴퓨터와 연결된 네트워크가 주어질 때, 1번 컴퓨터와 네트워크로 연결되어서 웜 바이러스에 걸리게 되는 컴퓨터의 수를 구하는 문제이다.

 

컴퓨터와 네트워크는 그래프의 정점과 간선으로 모델링 할 수 있고, 1번 정점과 연결된 연결 요소에 포함된 정점의 개수 - 1이 정답이 될 것이다. 연결 요소의 정점의 개수는 DFS 혹은 BFS로 정점들을 탐색하면서 구할 수 있다.

---

소스 코드

DFS

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

vector<int> E[101];
bool visited[101];
int answer = -1;

void dfs(int x) {
    answer++;
    visited[x] = true;

    for (auto next : E[x]) {
        if (visited[next]) continue;
        dfs(next);
    }
}

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

    int computer, edge, u, v;
    cin >> computer;
    cin >> edge;

    for (int i = 0; i < edge; i++) {
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(1);
    cout << answer << '\n';

    return 0;
}

 

BFS

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

vector<int> E[101];
bool visit[101];
int answer;

void bfs(int start_x) {
    queue<int> Q;
    Q.push(start_x);
    visit[start_x] = true;

    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for (auto next : E[cur]) {
            if (visit[next]) continue;
            Q.push(next);
            answer++;
            visit[next] = true;
        }
    }
}

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

    int computer, e, a, b;
    cin >> computer;
    cin >> e;

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

    bfs(1);

    cout << answer << '\n';

    return 0;
}