[BOJ/C++] 바이러스(2606번)

1. 개요

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

2606번: 바이러스

1-1. 설명

웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸린다. 어느 날, 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성한다

1-2. 제한 사항

 - 1첫 줄에 컴퓨터의 수가 주어지며, 컴퓨터의 수는 100 이하이고 1번부터 차례대로 번호가 매겨짐

 - 둘째 줄에 네트워크 상에서 연결되어 있는 컴퓨터 쌍의 수가 주어짐

 - 이어서 그 수만큼 한줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터 번호 쌍이 주어짐

---

2. 구현

2-1. 풀이

단순하게 DFS로 풀었더니 풀렸다. 

2-2. 코드

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

vector<int> graph[101];
int stack[1000];
bool check[101];
int result = 0;

void DFS(int start);

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

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

    DFS(1);

    cout << result - 1;
    return 0;
}

void DFS(int start) {
    int top = -1;
    stack[++top] = start;

    while (top != -1) {
        int cur = stack[top--];
        if (check[cur]) continue;
        check[cur] = true;
        result += 1;

        for (int i = 0; i < graph[cur].size(); i++) {
            int nextNum = graph[cur][i];
            stack[++top] = nextNum;
        }
    }
}