[C/C++] 백준 #2606 바이러스(너비 우선 탐색)

이번 문제는 깊이 우선 탐색(DFS)나 너비 우선 탐색(BFS)를 이용해서 첫번째 노드와 연결된 노드들의 갯수를 찾으면 됩니다.

 

computer virus

 

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

2606번: 바이러스

 

그래프 탐색을 이용하기 위해서는 인접 행렬이나 인접 리스트를 구성해주어야 합니다.  가변 리스트를 생성할 수 있다면, 인접 리스트를 사용하는 것이 편합니다.  인접 행렬은 간선의 개수가 \(O(N^2)\)에 이르는 경우에 구성하면 좋습니다.  그 외에는 인접 리스트를 사용한다고 보시면 됩니다.  저도 인접 리스트를 사용해서 문제를 풀었습니다.

 

보통은 간단한 문제의 경우에는 깊이 우선 탐색을 선호하는 편이지만, 여기서는 큐 자료구조를 이용해서 너비 우선 탐색을 이용해서 풀었습니다.

 

간단하게 너비 우선 탐색을 해서 방문한 노드의 개수만 알아내면 되는 문제라서, 기초적인 알고리즘만 알고 있으면 해결할 수 있습니다.

난이도도 실버 3 등급에 해당하니까요.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2606
//        - by Aubrey Choi
//        - created at 2019-08-01
//------------------------------------------------
#include <stdio.h>
#include <queue>
#include <vector>

int main()
{
    int n, m, s, t, ans = -1;
    char v[100];
    std::queue<int> q;
    std::vector<int> adj[100];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) v[i]=0;
    while(m--)
    {
        scanf("%d%d", &s, &t); s--, t--;
        adj[s].push_back(t);
        adj[t].push_back(s);
    }
    q.push(0);
    v[0]=1;
    while(!q.empty())
    {
        s = q.front(); q.pop();
        ans++;
        for(auto t : adj[s])
        {
            if(v[t]) continue;
            v[t]=1;
            q.push(t);
        }
    }
    printf("%d\n", ans);
    return 0;
}