득이공간

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

PS/알고리즘 문제풀이

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

쟁득 2024. 1. 24. 09:23
 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍

www.acmicpc.net

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