[백준 2606] 바이러스

0. 제목

• 백준 2606 바이러스
• BOJ 2606 바이러스
• C++ 2606 바이러스

---

1. 문제

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

---

2. 풀이

• 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
• dfs를 활용하여 연결되어 있는 컴퓨터들의 개수를 구한다. dfs내부에서 감염 컴퓨터 수를 세는 cnt 변수를 사용한다.
• 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터를 구하는 문제이기 때문에 dfs(1)을 수행하여 정답을 구할 수 있다.

---

3. 코드

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v[101];
int visited[101] = {0};
int cnt;
 
void dfs(int x){
    if(visited[x]) return;
    visited[x] = 1;
    cnt++;
    for(int i = 0; i < v[x].size(); i++){
        int y = v[x][i];
        dfs(y);
    }
}
 
int main(int argc, const char * argv[]) {
    int N, M;
    int a, b;
    
    cin >> N >> M;
    
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    dfs(1);
    cout << cnt - 1 << '\n';
    
    return 0;
}