[알고리즘/문제풀이][BOJ 2606번] 바이러스

바이러스 문제는 BFS를 이용하는 전형적인 문제이다. BFS의 특성인 "연결된 모든 노드를 찾는다"를 이용하여 1번 컴퓨터에서 출발하여 도달할 수 있는 모든 컴퓨터의 개수를 찾아야 한다. 이러한 특성을 이용한 기법을 "Flood Fill"이라고 한다. 보통 군집의 개수나 크기를 계산할 때 많이 사용한다.

BFS 코드의 템플릿은 다음의 글에서 참고할 수 있다. 해당 템플릿을 변형하면 많은 BFS 문제를 큰 고민없이 빠르게 해결할 수 있다.

2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

[알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

문제에 대해 작성한 코드는 다음과 같다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com/

int N;
int M;
int temp1, temp2;
int graph[200][200];
int visited[200];
int cnt;

int queue[1000];
int rp, wp;

void BFS() {
	visited[1] = 1;
	queue[wp++] = 1;

	while (rp!=wp) {
		int temp = queue[rp++];
		for (int i = 1; i <= N; i++) {
			if (i == temp) continue;
			if (graph[temp][i] == 0) continue;
			if (visited[i] == 1) continue;
			visited[i] = 1;
			cnt++;
			queue[wp++] = i;
		}
	}

}

int main(void) {
	scanf("%d", &N);
	scanf("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf("%d %d", &temp1, &temp2);
		graph[temp1][temp2]=1;
		graph[temp2][temp1] = 1;
	}

	BFS();

	printf("%d\n", cnt);
}