백준 2606번 "바이러스"

백준 2606번 “바이러스”

Question:

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

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

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

Input:

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

Output:

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

Restriction:

시간제한:
1 초

Example Case:

Input case 1:

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

Output case 1:

4

풀이 과정:
이 문제는 BFS를 활용한 기초적인 그래프 탐색 관련 문제이다.

BFS(Breadth-First Search) 그래프 탐색 방법은,
어떠한 임의의 노드에 인접한 노드를 우선적으로 방문하는 그래프 탐색방법이다.

자료구조중
“큐“를 활용하여 탐색을 진행하는데,
한 정점으로 부터 시작하여
“정점이 인접해 있고,해당 정점을 방문하지 않은 상태” 라면,
큐에 직접 해당 정점들을 enqueue한다.
그 후,
FIFO(First In First Out,선입선출)의 성질을 가진 큐에서 정점을 하나씩 dequeue 하며,
dequeue한 정점에 위에 똑같은 조건을 가진 정점을 다시 enqueue 시킨다.
이러한 과정을 반복하여
연결되어있는 모든 정점에 대해(큐가 empty()가 될 때까지) 탐색을 진행한다.

이 문제를 푸는 방법은,
BFS를 구현 한 뒤
해당 문제 조건에 맞게 정점 ‘1’부터 BFS를 진행한 뒤,
방문한 정점이 저장된 visited 배열을 확인해보자.

자료구조 큐
(참고 : https://crispy-down.github.io/2021/08/04/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2-%ED%81%90/)

#include <iostream>
#include <queue> 
using namespace std;
#define MAX 101 //컴퓨터 수는 100이하

int N,M; //정점의 개수,간선의 개수
int map[MAX][MAX]; //인접행렬 구현
bool visited[MAX]; //방문한 노드에 대한 관계 배열(방문했다면 bool = true)
queue<int> q; //큐 선언


void reset() { //방문한 노드 저장 배열 초기화
    for(int i = 1;i<=N;i++) {
        visited[i] = 0;
    }
}

void BFS(int v) {
    q.push(v); //v에 대해서 방문 + enqueue
    visited[v] = true;
    while(!q.empty()) {
        v = q.front(); //방문한 노드
        q.pop(); //dequeue 뒤 인접한 노드 and 방문안한 노드에 대하여 enqueue(방문)
        for(int w = 1; w<= N;w++) {
            if(map[v][w] == 1 && visited[w] == 0) { //해당 조건(인접 + 방문 x ==> 노드 w)
                q.push(w);
                visited[w] = true;
            }
        }
    }   
}


int main() {
    cin >> N;
    cin >> M;
    for(int i = 0;i<M;i++) {
        int a,b;
        cin >> a >> b;
        map[a][b] = 1; //간선을 입력 받은 뒤 인접 행렬 갱신
        map[b][a] = 1;
    }
    reset(); //초기화
    BFS(1); //BFS 실행

    int count = 0;
    for(int i = 1;i<=N;i++) {
        if(visited[i] == true) {
            count += 1; //방문한 노드 개수
        }
    }
    cout << count-1 << endl; 
    //1에서 BFS 시작,해당 문제 조건에 따라 1 제외 나머지 방문한 노드 개수 출력 == 정답
}

• 백준
• 문제풀이
• 알고리즘