[C++] 백준 2606번 풀이 ( 바이러스 )

- 문제 ( 2606번 ) : 바이러스

• 링크 : https://www.acmicpc.net/problem/2606

• 컴퓨터가 네트워크 상에서 그래프 형태로 연결되어있다. (양방향) 이 네트워크 속 1번 컴퓨터가 바이러스에 걸렸을 때 1번과 연결된 컴퓨터는 무조건 바이러스에 감염되게 된다.

  • 이때 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수를 구하는 프로그램을 작성하는 문제.

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄에 컴퓨터의 수 ( n ) 입력
• 둘째 줄에 네트워크 상 연결되어있는 edge 수 ( m ) 입력.
• 셋째 줄부터 m개 줄에 걸쳐 edge 입력

[ 출력 ]

• 1번 컴퓨터가 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수 출력

---

- 문제 풀이

• 이번 문제는 굉장히 간단하다.
  바이러스에 감염된 컴퓨터와 연결된 컴퓨터는 무조건 감염된다는 사실을 알고있으면 쉽게 해결된다.

  즉, 1번 컴퓨터에서 도달할 수 있는 모든 컴퓨터의 개수를 구하면, 1번 컴퓨터로 인해 바이러스에 걸리게 되는 컴퓨터의 수를 구할 수 있고, 어떠한 node 와 연결된 모든 node 를 탐색하는 방법이 dfs 이다.

• 컴퓨터는 방향이 없이 경로로 연결이 되어있으므로 양방향 graph 로 생각한 후 문제를 해결하면 된다.

  • 나는 이러한 양방향 graph 를 c++ 의 vector 자료구조를 사용해 구현했다.

    • 인접리스트 형식으로 구현.

• 양방향으로 node 를 연결해주고, 1번 컴퓨터부터 DFS 로 깊이우선탐색을 진행해주면 된다.

  탐색을 진행하면서 새로운 노드를 방문하면 즉, 방문하지 않았던 새로운 컴퓨터를 방문할때마다 컴퓨터의 개수를 1개씩 늘려나가면 된다.

• 최종적으로 1개씩 늘려나가던 컴퓨터의 개수를 출력하면 문제 해결!

---

- 최종 코드

#include <iostream>
#include <vector>
#define N_MAX 101
using namespace std;

// 컴퓨터의 수 n, 컴퓨터가 연결된 edge 의 수 m 선언
int n = 0, m = 0;

// 네트워크를 저장하는 graph 선언
vector<int> graph[N_MAX];

// 방문했는지 여부 확인하는 bool 배열 선언
bool is_visit[N_MAX] = {false, };

// 웜 바이러스에 걸리게 되는 컴퓨터의 수 저장 변수 선언
int number_of_com = 0;

void Search(int node) {
    for(int i = 0; i < graph[node].size(); i++) {
        // 현재 연결되어있는 모든 node 를 탐색
        int current = graph[node][i];

        // 방문하지 않은 node 라면
        if(!is_visit[current]) {
            is_visit[current] = true;
            number_of_com ++;
            Search(current);
        }
    }
}

int main() {
    // 컴퓨터의 수, 컴퓨터가 연결된 edge 의 수 차례로 입력
    cin >> n >> m;

    // m 개의 edge 입력
    for(int i = 0; i < m; i++) {
        int a = 0, b = 0;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // 1 번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 구해야하므로 1번부터 탐색
    is_visit[1] = true;
    Search(1);

    // 결과 출력
    cout << number_of_com << endl;
    return 0;
}