[BOJ/C++] 2606 : 바이러스

문제

www.acmicpc.net/problem/2606

2606번: 바이러스

 

풀이

DFS 가장 기본 문제.

1. 배열 만들기, 연결된 노드는 1로

2. depth 끝까지

3. 중복되지 않도록 visit 여부 확인

4. 1번 컴퓨터는 제외이므로 count-1 출력

 

 

코드

 

#include <iostream>
using namespace std;
int n, m;
int count=0;
int arr[201][201]={0};
int visit[101]={0};
void DFS(int depth){
    visit[depth]=1;
    count++;
    for(int i=1;i<=n;i++){
        if(arr[depth][i]==1 && visit[i]==0){
            DFS(i);
        }
    }
    
}
 
int main() {
    int a,b;
    scanf("%d %d", &n, &m);
    for(int i=0;i<m;i++){
        scanf("%d %d", &a, &b);
        arr[a][b]=1;
        arr[b][a]=1;
    }
    
    DFS(1);
    printf("%d",count-1);
    return 0;
}