백준 2606번 with cpp

백준 DFS 와 BFS 의 2606번 바이러스 문제

문제 링크 BAEKJOON Q_2606

우선 문제를 살펴보면 1번 컴퓨터로 인해 바이러스가 전파되고 연결되어 있지 않으면 영향을 받지 않는다.
그러니 바이러스에 감염되는 컴퓨터의 수를 출력하라.
이는 결국 1번과 연결되어 있는 노드를 탐색하라. 이다.
공부한 탐색이 BFS 와 DFS 이므로 이들 중 하나로 탐색을 하면 된다.

백준 사이트의 탐색문제 중 기초에 해당하므로 BFS 와 DFS 둘 다 사용해보자.

BFS 예시

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

vector<int> V[101];
int C[101];
int cnt;
void bfs(int x)
{
    queue<int> Q;
    Q.push(x);
     C[x] = true;
    while(!Q.empty())
    {
        int y = Q.front();
        Q.pop();
        for(int i = 0; i < V[y].size(); i++)
        {
            int z = V[y][i];
            if(!C[z])
            {
                C[z] = true;
                Q.push(z);
                cnt++;
            }
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        V[t1].push_back(t2);
        V[t2].push_back(t1);
    }
    bfs(1);
    cout << cnt;
    return 0;
}

DFS 예시

#include <iostream>
#include <vector>
using namespace std;

vector<int> V[101];
int C[101];
int cnt;
void dfs(int x)
{
    if(C[x]) return;
    C[x] = true;
    cnt++;
    for(int i = 0; i < V[x].size(); i++)
    {
        int y = V[x][i];
        dfs(y);
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        V[t1].push_back(t2);
        V[t2].push_back(t1);
    }
    dfs(1);
    cout << cnt - 1;
    return 0;
}

BFS

---

DFS