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

 

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 링크: https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

【 풀이 】

 

DFS(깊이 우선 탐색)이나 BFS(너비 우선 탐색)을 이용하여 간단히 해결할 수 있다.

DFS가 조금 더 간단하게 구현 가능하기에 DFS를 이용하여 해결했다.

 

방문 여부를 나타내는 배열과 인접 리스트(각 점에 인접한 점들을 나타내는 배열)를 선언하고

인접 리스트 각 노드의 깊이를 우선으로 반복문으로 돌려보면서 방문 여부를 체크하면 된다.

 

 

 

【 코드 】

#include<iostream>
#include<vector>
using namespace std;

bool visited[101];
vector<int>graph[101];

void dfs(int x)
{
	visited[x] = true;
	for (int i = 0; i < graph[x].size(); i++)
	{
		int y = graph[x][i];
		if (!visited[y])
			dfs(y);
	}
}
int main(void)
{
	int cnt = 0;
	int n, t;
	cin >> n >> t;
	for (int i = 1; i <= t; i++)
	{
		int num1, num2;
		cin >> num1 >> num2;
		graph[num1].push_back(num2);
		graph[num2].push_back(num1);
	}
	dfs(1);
	for (int i = 2; i <= n; i++)
	{
		if (visited[i])
			cnt++;
	}
	cout << cnt;
}