Easy is Perfect

[백준] 2606번 C/C++ 풀이 _ 바이러스

  • melonicedlatte
  • Feb 23, 2018


출처 : https://www.acmicpc.net/problem/2606 

바이러스 성공 풀이

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB153756110426938.505%

문제

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

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

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

입력

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

출력

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

예제 입력 

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

예제 출력 

4

힌트

출처

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 초등부 3번

  • 잘못된 데이터를 찾은 사람: jsa3824

알고리즘 분류

>> 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
typedef struct NODE { 
    vector<int>* co_node_vec;
}NODE;
 
// 노드 배열과 방문한 곳의 숫자를 넣는다. 
NODE** node_arr;
int* visited;
queue<int> computer_queue;
int answer = -1; 
 
// 1번 노드와 관련 있는 친구들을 센다. bfs로 구현한다. 
int bfs() {
    computer_queue.push(1);
    while (computer_queue.size()) { 
        // queue 에 있는 원소를 하나 빼고 나서 visited 를 1로 변경 
        int sub_node = computer_queue.front();
        computer_queue.pop();
 
        if (visited[sub_node] == 1) continue;
        visited[sub_node] = 1;
        answer++;
 
        // 뺀 노드와의 관계를 살펴보고, 연결된 노드들을 추가한다. 
        for (int i = 0; i < node_arr[sub_node]->co_node_vec->size(); i++) {
            computer_queue.push(node_arr[sub_node]->co_node_vec->at(i));
        }
    }
 
    return answer;
}
 
int main() {
    int total_node_num, relation_num; 
    cin >> total_node_num >> relation_num;
    
    // 노드 생성 _ 0번은 사용하지 않는다. 
    node_arr = (NODE**)malloc(sizeof(NODE*)*(total_node_num+1));
    visited = (int*)malloc(sizeof(int)*(total_node_num + 1));
    for (int i = 1; i <= total_node_num; i++) {
        node_arr[i] = (NODE*)malloc(sizeof(NODE));
        node_arr[i]->co_node_vec = new vector<int>;  
        visited[i] = 0; 
    }     
 
    // 관계 형성 
    int sub_node_1, sub_node_2;
    for (int i = 0; i < relation_num; i++) {
        cin >> sub_node_1 >> sub_node_2;
        node_arr[sub_node_1]->co_node_vec->push_back(sub_node_2);
        node_arr[sub_node_2]->co_node_vec->push_back(sub_node_1);
    }
 
    cout << bfs();
 
    return 0; 
}
cs



Search