[알고리즘 문제] 백준2606 - 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

dfs,bfs로 풀 수 있는데 저는 bfs로 풀었습니다. 각 노드들의 간선을 양방향으로 map먼저 체크해주었습니다.

1번 컴퓨터 부터 시작하기 때문에 que에 1번을 넣어주고 하나씩 꺼내면서 맵에 연결되어 있으면 그 다음 시작점을 que에 넣는 방식으로 진행하였습니다. 한번 방문한 노드는 다시 방문하면 안되기 때문에 visited[]로 체크해주었습니다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{

    int map[101][101] = {0};
    int node, edge;
    queue<int> que;

    cin >> node >> edge;

    for (int i = 0; i < edge; i++)
    {
        int a, b;
        cin >> a >> b;
        map[a][b] = map[b][a] = 1;
    }

    int visited[101] = {0};
    visited[1] = 1;
    int ans = 0;
    que.push(1);

    while (!que.empty())
    {
        int start = que.front();
        que.pop();

        for (int end = 1; end <= node; end++)
        {
            if (map[start][end] == 1 && !visited[end])
            {
                ans++;
                visited[end] = 1;
                que.push(end);
            }
        }
    }

    cout << ans << endl;
    return 0;
}