[백준] 2606번 바이러스 C++ 문제풀이

https://www.acmicpc.net/problem/2606

2606번: 바이러스

문제 풀이

dfs를 이용해 방문한 지점들에 대해서 check 배열을 true로 바꿔주었다.

check 배열의 true값의 갯수를 이용해서 count를 구했다.

소스 코드

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

bool check[101] = { false };
vector<int> graph[101];

void dfs(int idx) {
	if (check[idx] == false) {
		check[idx] = true;
		int size = graph[idx].size();
		for (int i = 0; i < size; i++) {
			int num = graph[idx][i];
			dfs(num);
		}
	}
}

int main() {
	int N, K;
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int s, e;
		cin >> s >> e;
		graph[s].push_back(e);
		graph[e].push_back(s);
	}

	dfs(1);

	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		if (check[i] == true) {
			cnt += 1;
		}
	}
	cout << cnt - 1 << '\n';
}