[백준] 2066. 바이러스

[문제]

 

www.acmicpc.net/problem/2606

2606번: 바이러스

 

[풀이]

 

1번 컴퓨터가 바이러스에 걸렸고 1번 컴퓨터와 연결된 컴퓨터는 모두 바이러스에 걸리게 된다.

이 때 1번은 제외하고 바이러스에 걸린 컴퓨터의 갯수를 출력하면 된다.

 

문제는 DFS를 사용해서 풀 수 있었다. map이라는 2차원 배열을 선언하여 연결 정보를 저장했다.

그 다음 DFS를 1번부터 시작하여 start와 연결된 모든 컴퓨터에 대해 DFS 함수를 호출한다.

visited를 통해서 이미 방문했는지 확인하고 , 방문하지 않은 경우에만 DFS 함수를 호출하였다.

 

이렇게 DFS 함수를 끝내고 visited가 1인 컴퓨터의 개수를 count하여 출력해주면 된다.

 

 

[코드]

 

시간 : 0ms

#include <iostream>
#define MAX 101
using namespace std;

int map[MAX][MAX]={0,};
int visited[MAX]={0,};
int N,M;

void DFS(int start)
{
    visited[start]=1;
    for(int i=2;i<=N;i++){
        if(map[start][i]==1 && visited[i]==0)  DFS(i);
    }
}

int main(void)
{
    int ans=0;
    
    cin >> N >> M;
    
    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        
        map[a][b]=1;
        map[b][a]=1;
        
    }
    
    DFS(1);
    for(int i=2;i<=N;i++){
        if(visited[i]==1)   ans++;
    }
    cout << ans;
    
    return 0;
    
}