[BOJ] 2606_바이러스 with cpp

# 생각

1번을 시작점으로 연결된 네트워크를 검사하면 되는 문제이므로

1차원 bfs를 이용하여 탐색을 하면 해결 가능하다

 

각 정점의 연결된 간선들은 2차원 배열을 통해 입력을 받고 양쪽다 1로 저장해주면

연결되어 있음을 표시할 수 있다

 

연결되어 있는 컴퓨터와 방문하지 않은 네트워크일 경우

바이러스에 걸리게 되는 컴퓨터의 수를 증가해주면 된다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

int graph[111][111], vis[111];

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		graph[x][y] = 1;
		graph[y][x] = 1;
	}

	queue<int> q;
	q.push(1);
	vis[1] = 1;
	int ans = 0;
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		for (int i = 1; i <= n; i++)
		{
			if (graph[cur][i] == 1 and vis[i] == 0)
			{
				q.push(i);
				vis[i] = 1;
				ans++;
			}
		}
	}
	cout << ans;
}

 

---

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

2606번: 바이러스