[c++]baekjoon 2606(바이러스)

www.acmicpc.net/problem/2606

2606번: 바이러스

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

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

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

---

BFS로 풀었을 경우 하나하나 따라가 보도록 하겠습니다. 

입력에 대한 matrix로 받았을 경우 입니다. 

7 computer input number
6  computer가 연결된 관계

1 2
2 3
1 5
5 2
5 6
4 7

 

computer 연결을 matrix로 입력 했을 때,

0 1 0 0 1 0 0 
1 0 1 0 1 0 0 
0 1 0 0 0 0 0 
0 0 0 0 0 0 1 
1 1 0 0 0 1 0 
0 0 0 0 1 0 0 
0 0 0 1 0 0 0 

 

1에서 부터 시작 했을 경우 
1 : 1을 지나갔다는 의미이미 
temp, i, mat[temp][i] , visited[i]1 1 0 1 ; 방문했고 mat = 0 이어서 skip
temp, i, mat[temp][i] , visited[i]1 2 1 0 ;방문 안했고 mat =1 이어서 queue에 2 push
temp, i, mat[temp][i] , visited[i]1 3 0 0 ;방문 안했고 mat =0 이어서 skip  
temp, i, mat[temp][i] , visited[i]1 4 0 0 ;방문 안했고 mat =0 이어서 skip
temp, i, mat[temp][i] , visited[i]1 5 1 0 ;방문 안했고 mat =1 이어서 queue에 5 push
temp, i, mat[temp][i] , visited[i]1 6 0 0 ;방문 안했고 mat =0 이어서 skip
temp, i, mat[temp][i] , visited[i]1 7 0 0 ;방문 안했고 mat =0 이어서 skip

--> for loop 완료되고 queue에서 하나 가져온다 

Queue 상태 

2

5

 

2 : queue에 저장된 것 가져오고 pop한 후 for loop 수행 
temp, i, mat[temp][i] , visited[i]2 1 1 1 ;방문 했고 mat =1 이어서 skip
temp, i, mat[temp][i] , visited[i]2 2 0 1 ;방문 했고 mat =0 이어서 skip
temp, i, mat[temp][i] , visited[i]2 3 1 0 ;방문 안했고 mat =1 이어서 queue에 3 push
temp, i, mat[temp][i] , visited[i]2 4 0 0 ;방문 안했고 mat =0 이어서 skip
temp, i, mat[temp][i] , visited[i]2 5 1 1 ;방문 했고 mat =1 이어서 skip
temp, i, mat[temp][i] , visited[i]2 6 0 0 ;방문 안했고 mat =0 이어서 skip
temp, i, mat[temp][i] , visited[i]2 7 0 0 ;방문 안했고 mat =0 이어서 skip

 

Queue 상태 

5

3

5 
temp, i, mat[temp][i] , visited[i]5 1 1 1 ;방문 했고 mat =1 이어서 skip
temp, i, mat[temp][i] , visited[i]5 2 1 1 ;방문 했고 mat =1 이어서 skip
temp, i, mat[temp][i] , visited[i]5 3 0 1 ;방문 했고 mat =0 이어서 skip
temp, i, mat[temp][i] , visited[i]5 4 0 0 ;방문 안했고 mat =0 이어서 skip
temp, i, mat[temp][i] , visited[i]5 5 0 1 ;방문 했고 mat =0 이어서 skip
temp, i, mat[temp][i] , visited[i]5 6 1 0 ;방문 안했고 mat =1 이어서 queue에 6 push
temp, i, mat[temp][i] , visited[i]5 7 0 0 ;방문 안 했고 mat =0 이어서 skip

 

Queue 상태 

3

6

3 
temp, i, mat[temp][i] , visited[i]3 1 0 1 ;방문해서 skip 
temp, i, mat[temp][i] , visited[i]3 2 1 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]3 3 0 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]3 4 0 0 ;mat=0이어서 skip
temp, i, mat[temp][i] , visited[i]3 5 0 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]3 6 0 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]3 7 0 0  ;mat=0이어서 skip

 

Queue 상태 

6

6 
temp, i, mat[temp][i] , visited[i]6 1 0 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]6 2 0 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]6 3 0 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]6 4 0 0 ;mat=0이어서 skip
temp, i, mat[temp][i] , visited[i]6 5 1 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]6 6 0 1 ;방문해서 skip
temp, i, mat[temp][i] , visited[i]6 7 0 0 ;mat=0이어서 skip
-1

 

더이상 queue에 남아있는 게 없어서 while문을 빠져나오고 끝난다. 

 

  1 /*baekjoon 2606 virus*/                                                                          
  2 #include <iostream>
  3 #include <queue>
  4 
  5 using namespace std;
  6 #define max 1001
  7 
  8 int n, m, start;// 정점수 , 간선수 , 시작점 
  9 int mat[max][max] = {0, };
 10 int count;
 11 
 12 bool visited[max] = { false, };
 13 
 14 void init(){
 15     for ( int i =0; i <= 1000; i++) { visited[i] = false;}
 16     count=0;
 17 }   
 18     
 19 
 20 void DFS(int st){ 
 21     visited[st] = true;
 22     //cout << st << " ";
 23     count++; 
 24     for (int i = 1; i <= n; i++) {
 25     //  cout << "st, i, mat[st][i] , visited[i]" << st << " "\
 26             << i << ' ' << mat[st][i] << ' ' << visited[i] << endl;
 27         if (mat[st][i] == 1 && visited[i] == false )
 28             DFS(i);
 29     }   
 30 
 31 }       
 32 
 33 void BFS(int st){
 34     queue<int> q; 
 35     visited[st] = true;
 36     q.push(st);
 37     
 38     while(!q.empty()) {
 39         int temp = q.front();
 40         cout << temp << " ";
 41         q.pop(); 
 42         for (int i = 1; i <= n; i++) {
 43     //      cout << "st, i, mat[temp][i] , visited[i]" << st << " "\
 44                 << i << ' ' << mat[temp][i] << ' ' << visited[i] << endl;
 45             if (mat[temp][i] == 1 && visited[i] == false ){
 46                 visited[i] = true;
 47                 q.push(i);
 48             }
 49         }
 50     }
 51 
 52 }
 53 
 54 int main(){
 55     ios_base::sync_with_stdio(0);
 56     cin.tie(0);
 57 
 58     int start = 1;
 59     cin >> n >> m ;
 60 
 61     for( int i=0; i < m; i++){
 62         int x,y;
 63         cin >> x >> y;
 64         mat[x][y] = 1;
 65         mat[y][x] = 1;
 66     }
 67 
 68 #if 0
 69     for( int i=1; i <= n; i++){
 70         for( int j=1; j <= n; j++){
 71             cout << mat[i][j] << ' ';
 72         }
 73         cout << endl;
 74     }
 75 #endif
 76 
 77     //cout << "DFS start!!" << '\n';
 78     init();
 79     DFS(start);
 80     cout << count-1 << endl;
 81 
 82     return 0;
 83 }
 84 /*baekjoon 2606 virus*/