[백준/C++] 2606번 바이러스

문제링크

2606번 바이러스

 

 

매우 친절하게도 그림으로 보여준다.

1번을 시작정점으로 하여 갈 수 있는 연결된 모든 정점의 수를 구하는 문제(완전탐색)

단, 정답에서는 1번 컴퓨터를 제외해야하므로 DFS를 통해 모든 방문노드의 수를 구하고 1을 빼주면 된다.

 

 

제출코드

#include <iostream>

using namespace std;
// 정점이 주어지고 간선이 주어졌을 때, 시작점으로부터 완전탐색하여 연결된 정점의 수를 모두 구함
// DFS 사용

int N, M, V;
int result = 0;
int arr[101][101];
bool visited[101];

void DFS(int V);

int main()
{
	int a, b; // 정점 a-b

	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;

		arr[a][b] = 1;
		arr[b][a] = 1;
	}

	DFS(1);
	cout << result - 1;	// 제일 첫번째 1은 포함하지 않음
	return 0;
}

void DFS(int V)
{
	visited[V] = 1;
	result++;

	for (int i = 1; i <= N; i++)
	{
		if (arr[V][i] == 1 && visited[i] == 0)
		{
			DFS(i);
		}
		if (i == N)
		{
			return;
		}
	}
}