[c++/백준] 2606 바이러스

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

2606번: 바이러스

내가 처음 접해보는 너비우선탐색, 깊이우선탐색 문제...

dfs, bfs 모두 사용해서 해결할 수 있다.

 

<dfs 재귀를 이용한 방법>

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

vector<int> map[101];
bool visited[101] = { false };	//방문 유무 파악
int ans = 0;

//재귀를 이용한 dfs
int dfs(int n) {
	for (int i = 0; i < map[n].size(); i++) {
		int k = map[n][i];

		if (visited[k] == false) {
			visited[k] = true;
			ans++;
			dfs(k);
		}
	}
	return 0;
}

int main() {
	int t, n;
	cin >> t >> n;

	//인접 리스트 만드는 과정
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		map[b].push_back(a);
		map[a].push_back(b);
	}

	visited[1] = true;
	dfs(1);


	cout << ans;
}