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

문제 링크

2606번: 바이러스

문제 요약

그래프가 주어질 때, 1번 정점으로부터 방문 가능한 정점의 수를 구해야 한다.

접근 방법

1번 정점부터 깊이 우선 탐색 또는 너비 우선 탐색을 돌리면 됩니다. 제 경우에는 깊이 우선 탐색을 이용해서 풀었습니다. 정점의 수가 적기 때문에 인접 리스트 대신에 인접 행렬을 이용해도 상관이 없습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int computer, edge, cnt;
bool visited[101];
vector<int> adj[101];

void dfs(int now)
{
	if (!visited[now])
	{
		visited[now] = true;
		cnt++;
	}

	for (auto& i : adj[now])
		if (!visited[i])
			dfs(i);
}

int main(void)
{
	cin >> computer >> edge;
	for (int i = 0; i < edge; i++)
	{
		int c1, c2;
		cin >> c1 >> c2;
		adj[c1].push_back(c2);
		adj[c2].push_back(c1);
	}

	dfs(1);
	cout << cnt - 1;
	return 0;
}