[C++] 백준 2606 바이러스 DFS, BFS

#include <iostream>
#include <vector>
#include <queue>

#define COMMAX 101

using namespace std;

int netNum, comNum;
vector<int> node[COMMAX];
bool visited[COMMAX];
int counts = 0;

void BFS(int curr);

int main()
{
	ios::sync_with_stdio(false);

	cin >> comNum;
	cin >> netNum;

	for (int i = 0; i < netNum; i++)
	{
		int temp[2];
		cin >> temp[0] >> temp[1];

		node[temp[0]].push_back(temp[1]);
		node[temp[1]].push_back(temp[0]);
	}

	BFS(1);

	cout << counts;
}

void BFS(int curr)
{
	queue<int> q;
	q.push(curr);
	visited[curr] = true;

	while (!q.empty())
	{
		int currNode = q.front();
		q.pop();

		for (int i = 0; i < node[currNode].size(); i++)
		{
			int nextNode = node[currNode][i];

			if (!visited[nextNode])
			{
				q.push(nextNode);
				visited[nextNode] = true;
				counts++;
			}
		}

	}
}

 

풀이

1. DFS나 BFS로 풀면 된다.
2. 유의사항은 1은 포함 안 한 나머지 감염된 PC들의 개수를 세면된다.
3. 양방향리스트를 사용한다.
4. 연결되어 있는 리스트안만 검색하므로 1부터 시작한 리스트만 모두 순회한다.

 

 

BFS 설명 :  chanheess.tistory.com/45

너비 우선 탐색 BFS

DFS 설명 : chanheess.tistory.com/25

깊이 우선 탐색_DFS