(백준/C++) 2606_바이러스

2606번: 바이러스 (acmicpc.net) 문제는 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 찾는 것입니다. 즉, 1번 컴퓨터에서 뻗어갈 수 있는 모든 정점들을 찾는 문제입니다.

이 문제는 그래프 문제로 깊이 우선 탐색(DFS, Depth-first search)나 너비 우선 탐색(BFS, Breadth-First Search) 중 아무거나 선택해서 풀 수 있습니다.

접근법

이 문제는 그래프 탐색 알고리즘을 사용해 풀 수 있습니다.

네트워크 상의 컴퓨터 연결 관계를 그래프로 표현할 수 있으며, 각 컴퓨터는 정점(vertex)으로, 컴퓨터 간의 연결은 간선(edge)으로 표현됩니다.

너비 우선 탐색 (BFS) 사용

1. 1번 컴퓨터가 시작 정점이 됩니다.
2. 시작 정점부터 시작하여 방문하지 않은 정점을 큐(queue)에 추가합니다.
3. 아직 방문하지 않은 정점이 존재하는 동안(큐가 비어있지 않은 동안), 큐에서 정점을 하나씩 꺼내 방문하고, 방문하지 않은 인접 정점을 큐(queue)에 추가합니다.
4. 이때, 방문을 할 때 카운트를 통해 방문한 정점의 수를 계산할 수 있습니다.

깊이 우선 탐색 (DFS) 사용

1. 1번 컴퓨터가 시작 정점이 됩니다.
2. 시작 정점부터 시작하여 방문하지 않은 정점을 스택(혹은 재귀적)으로 하나씩 방문합니다.
3. 이때, 방문을 할 때 정점에 대해 카운트를 통해 방문한 정점의 수를 계산할 수 있습니다. (만약 1번 정점을 포함해 카운트 되었다면, 1번 정점을 제외해야 합니다.)

---

풀이

BFS(너비 우선 탐색)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int ConnectedCounter(int start, const vector<vector<int>>& network)
{
	int counter = 0;
	vector<bool> visited(network.size(), false);
	queue<int> Q;

	// 시작 정점을 방문합니다.
	Q.push(start);
	visited[start] = true;

	while (!Q.empty())
	{
		int curr = Q.front();
		Q.pop();

		for(int next : network[curr])
		{
			if (!visited[next])
			{
				Q.push(next);
				visited[next] = true;
				counter++;
			}
		}
	}

	return counter;
}

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

	int N, E;
	cin >> N >> E;

	vector<vector<int>> network(N + 1);
	while (E--)
	{
		int u, v;
		cin >> u >> v;
		network[u].push_back(v);
		network[v].push_back(u);
	}

	cout << ConnectedCounter(1, network) << '\n';
}

DFS(깊이 우선 탐색)

#include <iostream>
#include <vector>
using namespace std;

void DFS(int vertex, const vector<vector<int>>& network, vector<bool>& visited, int& counter)
{
	visited[vertex] = true;
	counter++;

	for (int next : network[vertex])
	{
		if (!visited[next])
		{
			DFS(next, network, visited, counter);
		}
	}
}

int ConnectedCounter(int start, const vector<vector<int>>& network)
{
	int counter = 0;
	vector<bool> visited(network.size(), false);

	DFS(start, network, visited, counter);

	return counter - 1;
}

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

	int N, E;
	cin >> N >> E;

	vector<vector<int>> network(N + 1);

	while (E--)
	{
		int u, v;
		cin >> u >> v;
		network[u].push_back(v);
		network[v].push_back(u);
	}

	cout << ConnectedCounter(1, network) << '\n';
}