득이공간
[백준 C++] 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의 개수를 중복 없이 카운트했습니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 1260 DFS와 BFS - 깊이우선탐색, 너비우선탐색 (0) | 2024.01.25 |
---|---|
[백준 C++] 2667 단지번호붙이기 - 깊이우선탐색 (1) | 2024.01.24 |
[백준 C++] 1931 회의실 배정 - 그리디 (0) | 2024.01.23 |
[백준 C++] 1463 1로 만들기 - 다이나믹프로그래밍 (0) | 2024.01.22 |
[백준 C++] 1874 스택 수열 - 자료구조 (0) | 2024.01.20 |