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

2606번: 바이러스

cpp

#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의 개수를 중복 없이 카운트했습니다.