#2606 바이러스 (C++)

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

2606번: 바이러스

 

이 문제를 푸는데 이해가 안된다면, 먼저 LV2 문제인 #11724 연결 요소의 개수 (C++)을 보고 오는 것을 추천한다.

푸는 로직이 11724번과 거의 동일하다. 

 

문제 풀이는 다음과 같았다. 

(1) 연결된 모든 노드를 순회한다.

(2) 이때 1번 노드와 연결되어 있으며, 접근한 적이 없었던 노드 (Bool문이 false로 표시됨)을 발견하면, 해당 노드를 DFS한다. 

(3) 해당 노드를 DFS하기 이전, 바이러스에 걸린 컴퓨터의 갯수를 +1 해준다. 

 

문제가 비교적 단순하게 느껴진 이유는, 오로지 1번 컴퓨터에 연결된 컴퓨터만 바이러스에 전염되기 때문이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n = 0, m = 0, ans = 0, temp = 0;
bool check[101]{ false, };
vector<int> v[101];

void dfs(int i) {
    check[i] = true;
    for (int a = 0; a < v[i].size(); a++) {
        temp = v[i][a];
        if (check[temp] == false) {
            dfs(temp);
            ans++;
        }
    }
}

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

    cin >> n >> m;
    int a = 0, b = 0;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(1);

    cout << ans << "\n";

    return 0;
}

 

DFS는 익숙해질때까지 끊임없이 풀고싶다.