바이러스 [C++]
난이도: ⚪⚪⚪
문제 설명

문제 접근
- 바이러스는 연결된 컴퓨터에 전파되기 때문에 BFS 또는 DFS를 이용하여 연결된 컴퓨터를 구한다.
- 연결된 컴퓨터를 한 쌍씩 입력받기 때문에 인접 리스트를 만들어 탐색한다.
- 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수를 구하면 되기 때문에 1번 컴퓨터부터 DFS를 실행해 재귀되는 횟수로 전염되는 컴퓨터의 수를 구할 수 있다.
제출 코드
#include <iostream>
#include <vector>
using namespace std;
vector<int> computers[101];
bool infected[101];
int cnt = -1;
void DFS(int computer_number)
{
infected[computer_number] = true;
cnt++;
for(int i = 0; i < computers[computer_number].size(); i++)
if(!infected[computers[computer_number][i]])
DFS(computers[computer_number][i]);
}
int main(void)
{
int computer_number, edge;
cin >> computer_number >> edge;
int num1, num2;
for(int i = 0; i < edge; i++)
{
cin >> num1 >> num2;
computers[num1].push_back(num2);
computers[num2].push_back(num1);
}
DFS(1);
cout << cnt;
return 0;
}
결과