백준 바이러스(2606)

dfs,bfs를 활용하여 1을 제외한 노드를 탐색할 때마다 개수를 1개씩 누적하여 이를 출력하는 프로그램을 작성하는것이 문제의 요지이다. 미로찾기처럼 중간에 답이 있는것이 아닌, 모든 노드를 탐색해야하는 문제이다. 그렇기에 큐를 쓰는 bfs알고리즘보다는 dfs를 활용하여 간단하게 코드를 작성하였다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> nodes[101];
int visited[101] = { 0, };
int cnt = 0;

void	dfs(int i)
{
	for (int j = 0; j < nodes[i].size(); j++)
	{
		if (visited[nodes[i][j]] == 0)
		{
			cnt++;
			visited[nodes[i][j]] = 1;
			dfs(nodes[i][j]);
		}
	}
	return;
}

int main()
{
	int node_cnt;
	int link_cnt;
	int node_i;
	int link;

	scanf("%d", &node_cnt);
	scanf("%d", &link_cnt);

	for (int i = 1; i <= link_cnt; i++)
	{
		
		scanf("%d %d", &node_i, &link);
		nodes[node_i].push_back(link);
		nodes[link].push_back(node_i);
	}
	visited[1] = 1;
	dfs(1);
	printf("%d", cnt);
}