[C++] 백준 2606 바이러스

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

2606번: 바이러스

 

1. 서론

 

그래프를 이용해서 푸는 BFS, DFS 문제!!

 

 

2. 문제 풀이

 

한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 연결된 모든 컴퓨터는 바이러스에 걸린다. 컴퓨터는 1번부터 번호가 차례대로 매겨지며, 1번 컴퓨터가 바이러스에 걸렸을 경우 1번을 제외한 몇 개의 컴퓨터가 감염되는가를 찾는 것이 문제이다. 컴퓨터가 몇 개인지, 연결되어 있는 컴퓨터 쌍의 수가 입력으로 주어지며 그 뒤로 연결된 컴퓨터 번호의 한 쌍이 주어진다. 

 

딱 봐도 그래프를 활용하는 문제라서 난 평소에 그래프 활용하는 문제 나오면 어떻게 푸는지 모르겠어서 BFS 구현 코드를 찾아봤다. 

 

 

https://hongku.tistory.com/156

알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘

 

이 블로그에 있는 코드를 활용해서 문제를 풀었다. 어떤 원리로 돌아가는지 손으로 직접 해보니까 이렇게 해서 이런 결과가 나오는가 나는 알겠는데 여전히 왜, 어떻게 구현해야 하는지는 모르겠는... 그냥 외우면 된다^^

 

2차원 배열에 컴퓨터 번호 한 쌍을 입력하는데 예를들어 2번과 5번 컴퓨터가 연결되어 있으면 2번 배열과 5번 배열에 각자 5와 2라고 값을 넣어서 어떤 컴퓨터가 어떤 컴퓨터와 연결되어 있는지 배열에 저장한다. 그 후가 관건인데 이 문제는 결국 1번 컴퓨터와 연결된 컴퓨터는 몇 개인가를 찾는 문제이다. 결국엔 각 배열에 있는 값들을 다 확인해야 하는데 하나의 컴퓨터가 여러 개의 컴퓨터들과 연결되어 있으므로 모든 배열을 그냥 방문하면 중복되어 count 된다. 그러므로 BFS 알고리즘을 활용해야 한다. 위의 코드를 활용해서 큐에 배열에 있는 값들을 넣고 방문한 곳은 방문했다고 표시를 해주고 배열을 다 돌고 나면 큐의 맨 앞의 값을 빼는 방식이다. 큐가 빌 때까지 이 작업을 반복하면 1번 컴퓨터와 연결된 모든 컴퓨터들에 중복 없이 방문할 수 있다.

 

 

 

 

3. 코드 설명

 

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int cnt = -1;
int visit[10000];
vector<int> v[101];

void bfs(int s)
{
    queue<int> q;
    q.push(s);
    visit[s] = true;

    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        cnt++;
        for (int i = 0; i < v[x].size(); i++)
        {
            int y = v[x][i];
            if (!visit[y])
            {
                q.push(y);
                visit[y] = true;
            }
        }
    }
}
int main()
{
    int i, a, b, c, n;

    cin >> c >> n;

    for (i = 0; i < n; i++)
    {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    bfs(1);
    cout << cnt << endl;
}

 

값들을 입력받고 2차원 배열에 넣어준다. 그리고 bfs 함수에 넣는다.

bfs 함수에서 큐를 만들고 넘어온 매개변수는 큐에 넣고 이미 방문했다고 true로 체크한다.

그리고 큐에 들어있는 값에 해당하는 n번째 배열을 한 바퀴 돌면서 그 배열안에 있는 값에 방문을 안 했으면 큐에 그 값을 넣고 방문을 했다고 표시한다. 이렇게 한 바퀴 돌고 나면 n번에 있는 배열의 값을 다 보게 되기 때문에 큐의 맨 앞의 값은 pop 하고 다시 그 뒤의 n번째 배열을 한 바퀴 돌면서 방문한 적이 있는지 없는지 확인한 후 맨 앞의 값을 pop 한다. 이 과정을 큐의 값이 없을 때까지 반복하며 cnt변수에 count 해준다. cnt 가 -1부터 시작하는 이유는 1번 컴퓨터 자신의 값도 포함해서 count 하기 때문에 제외하기 위해 설정한 값이다.