문제

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

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

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

풀이

1. bfs 구현을 위한 q 구현
2. graph 구현
3. bfs
4. bfs를 하면서 탐색한 노드 카운트
5. 카운트 출력

코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
#define MAX_NODES 101

struct QueueType{
    int queue[MAX_QUEUE_SIZE];
    int front,rear;
};

struct GraphType{
    int graph[MAX_NODES][MAX_NODES];
    int n;
};

struct QueueType q;
struct GraphType g;

void queue_init(){
    q.front = q.rear = 0;
}

int is_empty(){
    return (q.front == q.rear);
}

int is_full(){
    return ((q.rear + 1) % MAX_QUEUE_SIZE == q.front);
}

void enqueue(int data){
    if(is_full(q))
        printf("overflow");
    q.rear = (q.rear + 1) % MAX_QUEUE_SIZE;
    q.queue[q.rear] = data;
}

int dequeue(){
   if(is_empty(q))
        printf("underflow");
    q.front = (q.front + 1) % MAX_QUEUE_SIZE;
    return q.queue[q.front]; 
}

void init_graph(){
    for(int i = 0; i < g.n; i++){
        for(int j = 0; j < g.n; j++){
            g.graph[i][j] = 0;
        }
    }
}

void insert_edge(int start, int end){
    if(start >= g.n || end >= g.n){
        fprintf(stderr,"vertex key error\\n");
        printf("start = %d, end = %d\\n", start, end);
        return;
    }
    g.graph[start][end] = 1;
    g.graph[end][start] = 1;
}

int bfs_virus(int v){
    int visited[g.n];
    for (int i = 0; i < g.n; i++) {
        visited[i] = 0;
    }

    
    int count = 0;
    visited[v] = 1;
    // printf("visit %d-> ", v);
    enqueue(v);
    while(!is_empty()){
        v = dequeue();
        for(int i = 0; i < g.n; i++){
            if(g.graph[v][i] && !visited[i]){
                visited[i] = 1;
                enqueue(i);
                // printf("visited %d-> ", i);
                count++;
            }
        }
    }
    // printf("\\n");
    return count;
    
}

int main(){
    queue_init();
    init_graph();
    scanf("%d", &g.n);
    g.n++;
    int edge_size, a, b;
    scanf("%d", &edge_size);
    for(int i = 0; i < edge_size; i++){
        scanf("%d %d", &a, &b);
        insert_edge(a, b);
    }
    printf("%d", bfs_virus(1));
    return 0;
    
}