C++ / 백준 / 2606 / 바이러스

문제

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

2606번: 바이러스

 

문제풀이

전형적인 DFS문제이다.

입력받는 값들을 표처럼 virus벡터에 push한다.

문제에서 1번 컴퓨터 부터시작하라 했으므로 DFS(1)을 실행하여 1부터 시작한다.

DFS함수를 실행했으면 visit벡터에 방문한걸 표시하고 크기만큼 반복해서 깊이탐색을 시작한다.

방문안한 노드를 발견하면 DFS를 하고 answer값에 1을 더한다.

1->2

2->3

3번 컴퓨터랑 연결된 2번 컴퓨터는 이미 방문했으므로 다시 2번 컴퓨터로 돌아간다.

2->5

5->6

다시 5번으로 돌아간다. 다시 2번으로 돌아간다. 다시 1번으로 돌아간다.

1번 컴퓨터와 연결된 컴퓨터는 모두 방문했으므로 종료한다.

 

코드

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

vector<vector<int>>virus;
vector<bool>visit;
int answer = 0;

void DFS(int start) {
	visit[start] = true;
	for (int cnt = 0; cnt < virus[start].size(); ++cnt) {
		if (!visit[virus[start][cnt]]) {
			DFS(virus[start][cnt]);
			answer++;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int computer = 0;
	int pair = 0;
	int y = 0, x = 0;
	int num1 = 0, num2;
	cin >> computer;
	cin >> pair;
	virus = vector<vector<int>>(computer+1, vector<int>(0, 0));
	visit = vector<bool>(computer+1, false);

	for (y = 0; y < pair; ++y) {
		cin >> num1 >> num2;
		virus[num1].push_back(num2);
		virus[num2].push_back(num1);
	}
	
	DFS(1);

	cout << answer;
}