[BOJ 2606] 바이러스

문제 출처

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

dfs, bfs고민하다 bfs로 푼 문제

1번 컴퓨터와 연결된 모든 컴퓨터의 갯수를 출력하는 문제이다.

dfs보다 bfs가 더 빠를 것이라 예상 되었다.

기본적으로 bfs 또는 dfs를 연습할 수 있는 문제

점점 문제를 풀수록 문제 이해를 하면 dfs bfs구현자체가 정형화 되있기 때문에 익숙해 지는 기분이다.

아직 많이 부족하다는 반증일수도....

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101
using namespace std;
int com;
int couple;
bool network[MAX][MAX];
bool visit[MAX];
queue<int> q;
int cnt=0;
 
void init() {
    scanf("%d", &com);
    scanf("%d", &couple);
    
    for(int i=1; i<=couple; i++) {
        int s, e;    //start end
        scanf("%d %d", &s, &e);
        network[s][e]=true;
        network[e][s]=true;
    }
}
 
void bfs(int s) {
    q.push(s);
    visit[s]=true;
 
    while(!q.empty()) {
        int s = q.front();
        q.pop();
 
        for(int i=1; i<=com; i++) {
            if(network[s][i] && network[i][s] && !visit[i]) {
                visit[i]=1;
                q.push(i);
                cnt++;
            }
        }
    }
}
 
int main(void) {
    init();
    bfs(1);
    cout<<cnt;
    return 0;
}