[알고리즘] DFS/BFS 활용 ⑧

[boj. 2606] 바이러스

1. 개요

1) 문제 개요

• 무방향 간선 그래프에서 DFS/BFS를 통해 연결된 모든 정점의 개수를 탐색할 수 있다.

2) 입출력

• 첫 째줄에 컴퓨터(정점)의 수가 주어진다.컴퓨터의 번호는 1번부터 차례로 매겨진다.
• 둘 째줄에는 컴퓨터 간 연결된 정보(간선)가 주어진다.
• 이어서 간선의 수 만큼 연결된 컴퓨터의 정보(컴퓨터 번호)가 주어진다.

2. Solution I.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int c = 0;    // 컴퓨터의 개수
int l = 0;    // 간선(연결) 개수
map<int, vector<int>> mp;
map<int, bool>v;// 컴퓨터 번호 별 방문 여부
int cnt = 0;

// 현재 컴퓨터 번호-와 연결된 모든 컴퓨터를 탐색
void dfs(int cur)
{
    for (int k = 0; k < mp[cur].size(); k++)
    {
        int connected = mp[cur][k];
        if (v[connected] == false)
        {
            cnt++;
            v[connected] = true;
            dfs(connected);
        }
    }
}

int main()
{
    cin >> c >> l;
    for (int k = 0; k < c; k++)v[k + 1] = false;

    for (int k = 0; k < l; k++)
    {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    v[1] = true;
    dfs(1);
    cout << cnt << endl;
    return 0;
}