[C++] 백준 2606 : 바이러스

#include <iostream>
#include <queue> // bfs
using namespace std;

int V, E; // vertex, edge

int map[101][101] = {0}; // 간선 저장
bool visited[101] = {false}; // 방문 여부
queue<int> q;

int cnt = 0; // 바이러스에 걸린 컴퓨터 수

void BFS(int n){
    if(!visited[n]){
        visited[n] = true; // 방문 체크
    }
    q.push(n); // 큐에 첫번째 노드 넣기

    while(!q.empty()){
        int vertex = q.front(); q.pop();

        for(int i=1; i<=V; i++){
            if(map[vertex][i] == 1 && !visited[i]){ // 간선 연결되어있고 방문되지 않았을 경우
                visited[i] = true; // 연결된 노드 방문
                q.push(i); // 노드 큐에 넣기
                cnt++; // 감염된 컴퓨터 개수 세기
            }
        }
    }
}

int main(int argc, char **argv){
    scanf("%d %d",&V,&E);

    int a, b;
    for(int i=1; i<=E; i++){
        scanf("%d %d",&a,&b);
        map[a][b] = 1;
        map[b][a] = 1; // 간선 연결, 방향 없음
    }

    BFS(1); // 1번 컴퓨터 감염 확인

    printf("%d", cnt);

    return 0;
}

BFS 연습용 문제.
인터넷 검색 없이 내 힘으로 풀 수 있었다 만세!!

BFS를 하면 간선이 연결되어있는 모든 노드를 검색한다. 1번 컴퓨터가 감염되었으므로 노드 1에서 BFS를 실행하면 된다. 그러면 1번 컴퓨터와 연결되어있는 모든 컴퓨터를 너비 우선 탐색으로 풀 수 있다(DFS도 가능)
만약에 간선이 연결되어있지 않으면 감염되지 않으므로 다른 노드들은 검사하지 않아도 된다. 연결된 노드의 수를 세면 된다.

좋은 웹페이지 즐겨찾기