[C++] 백준 2606: 바이러스

안녕하세요. 오늘 풀어볼 문제는 백준 바이러스입니다.

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

 

이 문제는 간단한 DFS 또는 BFS 문제입니다.

 

DFS는 깊이 우선 탐색인데요.

연관된 요소의 수준을 우선으로 가장 깊게 탐색하는 알고리즘입니다.

 

BFS는 넓이 우선 탐색입니다.

요소의 특정 수준을 모두 탐색한 후 다음 수준으로 넘어가는 알고리즘입니다.

 

저는 DFS를 사용했어요.

 

2차원 배열을 사용해서 네트워크의 위상을 표시해줬습니다.

DFS로 위상을 따라가며 감염되지 않은 컴퓨터의 수를 하나씩 세어줬어요.

 

주의해야할 점은 '1번이 감염시킨 컴퓨터 수'를 구하는 것이기 때문에 1번을 포함하면 안되는데요.

DFS를 하기 전에 감염 여부를 판단하는 배열에 표시를 해줬습니다.

 

#include <iostream>
using namespace std;

int N, M, cnt = 0;
int net[105][105];
int infected[105];

void f(int n) {
	for (int i = 1; i <= 100; i++) {
		if (net[n][i] == 1 && infected[i] != 1) {
			infected[i] = 1;
			cnt++;
			f(i);
		}
	}
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		net[a][b] = 1;
		net[b][a] = 1;
	}

	infected[1] = 1;
	f(1);

	cout << cnt;
}