[백준] 2606번: 바이러스

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

2606번: 바이러스

간단한 traverse 문제이다.

bfs를 쓰던, dfs를 쓰던 상관이 없을 것 같지만 dfs가 상대적으로 코드가 짧고 간편하니까 dfs를 사용해보았다.

//num 2606

#include <iostream>
#include <vector>

using namespace std;

vector<int> graph[101];
int visited[101];
int count = 0;

void dfs(int x){
	
	if(visited[x]==true){
		return;
	}
	visited[x] = true;
	cout << "visited: " << x << endl;
	count++;
	for(int i = 0; i<graph[x].size(); i++){
		int y = graph[x][i];
		if(visited[y]!=true){
			dfs(y);
		}
	}
}

int main(void){
	
	int n, m;
	cin >> n;
	cin >> m;
	cin.ignore();
	
	int start, end;
	for(int i = 0; i<m; i++){
		cin >> start >> end;
		cin.ignore();
		graph[start].push_back(end);
		graph[end].push_back(start);
	}
	
	dfs(1);
	
	cout << count-1 << endl;
}

방문할 때마다 count 를 증가시켜서 몇 개가 감염됐는지 체크하면 된다.

이렇게 하면 출발점인 1도 count에 추가되기 때문에, 정답을 출력할 때는 1을 빼주었다.