[백준/c++] 2606 바이러스

 

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

2606번: 바이러스

 

✨ 문제 풀이

간단한 BFS 해결 문제입니다. u와 v의 컴퓨터가 연결되어 있다면 u번째 배열에 v를 저장해주고, 마찬가지로 v번째 배열에 u를 저장해줍니다. 그리고 1번 컴퓨터와 연결되어 있는 모든 컴퓨터를 찾아야 하므로 BFS를 통해 연결된 컴퓨터를 하나씩 방문하면서 개수를 세어나갑니다. 이때 주의할 점은 1번에 영향을 받은 컴퓨터의 개수를 찾는 것이므로 1번 컴퓨터를 제외한 개수를 출력해야 합니다. 

 

🗓 코드

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

using namespace std;

#define MAXINT 101

int n, m;
vector<int> node_v[MAXINT];
bool visited[MAXINT];

void getInput()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        node_v[u].push_back(v);
        node_v[v].push_back(u);
    }
}

void solve()
{
    int result = -1;

    queue<int> next_node;
    next_node.push(1);
    visited[1] = true;

    while (!next_node.empty())
    {
        int current_node = next_node.front();
        next_node.pop();

        for (int i = 0; i < node_v[current_node].size(); i++)
        {
            int linked_node = node_v[current_node][i];
            if (!visited[linked_node])
            {
                next_node.push(linked_node);
                visited[linked_node] = true;
            }
        }
    }
    printf("%d\n", result);
}

int main(int argc, char const *argv[])
{
    getInput();
    solve();
    return 0;
}