[BFS] BOJ 2606번 바이러스

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

2606번: 바이러스

- 문제 파악

컴퓨터는 1번부터 100번까지 넘버링된다. 1번 컴퓨터에는 바이러스가 존재하고 이 바이러스는 연결된 컴퓨터에 전파된다. 임의의 개수 만큼 서로 연결된 컴퓨터가 입력될 때, 바이러스에 감염된 컴퓨터의 개수를 출력하라.

 

- 정답

BFS에서 가장 중요한건 내가 들렸던 곳을 체크하는 것이다.

전체적인 로직은 맞음에도 이것을 제대로 처리를 안했더니 초반부터 틀렸다... 

 

#include "bits/stdc++.h"

using namespace std;

int arr[102][102];
int check[102];


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    int ans = 0;
    int n, k;
    cin >> n;
    cin >> k;

    for (int i = 0; i < k; i++)
    {
        int a, b;
        cin >> a >> b;
        arr[a][b] = 1;
        arr[b][a] =1;

    }

    queue<int> q;
    q.push(1);
    check[1] = 1;

    while (!q.empty())
    {
        int pos = q.front();
        q.pop();
     
        for (int i = 1; i <= n; i++)
        {
            if (i == pos) 
                continue;

            if (arr[pos][i] && !check[i])
            {
                q.push(i);
                ans++;
                check[i] = 1;
                
            }
        }
    }

    cout << ans;

}