[백준 C++] 2606 바이러스 - 깊이우선탐색

2606번: 바이러스

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

vector<vector<int>> PCList;
vector<bool> CheckList;

int SpreadVirus(int SourcePC)
{
	int Infected = 1;
	CheckList[SourcePC] = true;
	
	for (const int& DestinationPC : PCList[SourcePC])
	{
		if (!CheckList[DestinationPC])
		{
			Infected += SpreadVirus(DestinationPC);
		}
	}

	return Infected;
}

int main()
{
	int MaxPC;
	cin >> MaxPC;

	PCList.reserve(MaxPC);
	for (int i = 0; i < MaxPC; ++i)
	{
		PCList.emplace_back(vector<int>());
	}

	CheckList.reserve(MaxPC);
	for (int i = 0; i < MaxPC; ++i)
	{
		CheckList.emplace_back(false);
	}

	int MaxPair;
	cin >> MaxPair;
	for (int i = 0; i < MaxPair; ++i)
	{
		int SourcePC = 0, DestinationPC = 0;
		cin >> SourcePC >> DestinationPC;
		PCList[SourcePC - 1].emplace_back(DestinationPC - 1);
		PCList[DestinationPC - 1].emplace_back(SourcePC - 1);
	}

	cout << SpreadVirus(0) - 1;
}

---

 

재귀함수(DFS)로 풀었습니다.

그래프를 인접 리스트 벡터로 표현한 다음

노드 방문 여부 체크 배열을 이용해서

감염된 PC의 개수를 중복 없이 카운트했습니다.