[DFS] 백준 2606번 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

수행기간 : 2021/01/15~01/15

벌써 DFS/BFS 본격 문제풀이에 들어간지 한주가 지나간다. 내가 첫 문제를 풀때 말했던 벡터에 익숙해지기는 아직도 힘든가보다.. 이번에는 map과 visit을 벡터로 구현하여 정적배열들을 좀 쓰지 않고 풀고 싶었는데 아쉽다.. 돌아오는 주에는 꼭 배열을 쓰지 않으려고 노력해보려 한다.

이 문제는 사실 한가지만 생각하면 쉬운 DFS에 속한다. 컴퓨터가 감염되는 문제이므로 감염컴퓨터를 찾을 때마다 count변수를 증가시켜주는 것만 기억하면 된다.

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;

//vector<vector<int>> map;
int visit[101];
int map[101][101];
int n, edge; //n<=100
int cnt = 0; //바이러스 감염 컴퓨터 수 카운터


void dfs(int x) {
	cnt++;
	visit[x] = true;
	for (int i = 1; i <= n;i++) {
		if (!visit[i] && map[x][i]) {
			dfs(i);
		}
	}
}
int main() {
	cin >> n >> edge;
	int a, b;
	for (int i = 0; i < edge;i++) {
		cin >> a >> b;
		map[a][b] = map[b][a] = true;
	}
	dfs(1);
	cout << cnt - 1;
}