백준 2606 - 바이러스 C++

"1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수"를 출력하는 문제입니다.

1번 노드부터 몇 개의 노드가 연결됐는지 확인하면 됩니다. DFS는 시작 노드로부터 연결돼있는 모든 노드를 방문합니다. DFS를 사용하면 쉽게 풀 수 있는 문제입니다. 

#include <iostream>
#include <vector>

using namespace std;

bool c[101];
vector<int> a[101];
int answer = 0;
void dfs(int x) {
	if (c[x]) return;
	c[x] = true;
	answer++;
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		dfs(y);
	}
}
int main(void) {
	int computer, line, u, v;
	cin >> computer >> line;

	for (int i = 0; i < line; i++) {
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs(1);
	cout << answer - 1;
	return 0;
}

1. main

가장 먼저 computer의 수, line의 수를 받고 그다음 줄에 네트워크 쌍을 입력받습니다. a[u]에서도 push_back을 a[v]에서도 push_back을 하는 이유는 2 5라고 입력받았을 때 2에서도 5를 갈 수 있어야 하지만 5에서도 2를 가야 하기 때문입니다. 

왼쪽 a[v].push_back(u)를 주석처리, 오른쪽 주석처리하지 않음

사진을 보면 쉽게 이해가 가능합니다.

 

2. dfs

c는 방문했는지 확인하는 배열입니다. 방문을 했으면 return으로 함수 종료, 방문하지 않았으면 true값으로 변경합니다. a[1].push_back(2), a[1].push_back(3) 이런 식으로 매번 push를 했을 때 1에 대해서는 그 사이즈인 2만큼 반복을 하고, i값을 바꾸면서 2, 3을 접근합니다. 그리고 그 값으로 다시 dfs 탐색을 합니다.

 

1을 포함해서 탐색했기 때문에 answer에서 -1을 한 값을 출력합니다.