(매일 BOJ) C++ 2606번 바이러스

이번 문제는 2606번 바이러스다.

문제 개요

컴퓨터가 네트워크로 연결되어 있을 때, 1번 컴퓨터가 바이러스에 걸렸을 경우 몇 대의 컴퓨터가 추가로 감염되는지를 구하는 문제입니다.

• 모든 컴퓨터는 서로 직접 또는 간접적으로 연결되어 있을 수 있음
• 입력으로 연결 관계가 주어지며, 양방향
• 1번 컴퓨터가 바이러스에 감염될 때, 감염되는 컴퓨터 수(1번 제외)를 구해야 합니다.

접근법

이 문제는 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용하여 1번 컴퓨터에서 시작해 연결된 모든 노드를 탐색하면 해결할 수 있습니다.

이 글에서는 DFS를 사용함

 

• 방문한 노드를 기록할 visit_dfs 배열(또는 벡터)을 사용하여 중복 방문을 방지
• 각 컴퓨터의 연결 정보를 저장하는 인접 리스트(벡터 배열)를 사용
• DFS로 재귀 호출하며 연결된 컴퓨터 수를 count
• 최종적으로는 시작점인 1번 컴퓨터를 제외한 수를 출력

작성코드

#include <bits/stdc++.h>
using namespace std;

void DFS (vector<bool> &,vector<int>*,int,int*);

int main(void){
    int com_num;
    cin >> com_num;
    int n;
    cin >> n;
    vector<int> v[com_num+1];
    for(int i = 1; i <= n; i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int j = 1; j <= com_num; j++){
        sort(v[j].begin(),v[j].end());
    }

    vector<bool> visit_dfs(com_num + 1);

    int result = 0;
    DFS(visit_dfs, v, 1, &result);

    cout << result;

}

void DFS (vector<bool>& visit_dfs, vector<int>* v,int num, int* result){
    visit_dfs[num] = 1;
    

    for(int i : v[num]){
        if(!visit_dfs[i]) {
            *result += 1;
            DFS(visit_dfs,v,i, result);
        }
    }
}