[알고리즘/BFS] 백준 2606번: 바이러스 - C/C++

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

2606번: 바이러스

 

- BFS 를 이용하였으며, Queue를 직접 구현하였습니다.

 

#include <stdio.h>

bool computer[101][101];
int queue[101];
bool visited[101];

int main() {
	int computerN;
	scanf("%d", &computerN);

	int linkN, a, b;
	scanf("%d", &linkN);

	for (int i = 0; i < linkN; ++i) {
		scanf("%d %d", &a, &b);
		computer[a][b] = true;
	}

	int ret = 0, R = 0, L = 0;

	visited[1] = true;
	for (int i = 1; i <= computerN; ++i) {
		if (computer[1][i] || computer[i][1]) {
			queue[R++] = i;
			visited[i] = true;
		}
	}
	
	while (R > L) {
		int current = queue[L++];
		++ret;

		for (int i = 1; i <= computerN; ++i) {
			if (visited[i]) continue;
			if (computer[current][i] || computer[i][current]) {
				queue[R++] = i;
				visited[i] = true;
			}
		}
	}
	printf("%d", ret);
}