[백준] 2606. 바이러스

2606. 바이러스

DFS 혹은 BFS로 푸는 문제였다.
큐를 사용하여 BFS로 풀었다.

1. 입력을 받고, 2차원 배열을 만들어 서로 연결된 컴퓨터에 1을 마킹한다.
2. 방문한 컴퓨터인지 아닌지 확인하는 visit 배열을 만든다.
3. 큐를 만들어 1번 컴퓨터를 넣고 for문으로 1번과 연결된 컴퓨터 중 방문하지 않은 컴퓨터를 큐에 넣고 count를 1 증가 시킨다.
4. 3번 과정을 큐가 빌때가지 반복한다.

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

bool visit[101];	// True이면 방문한 컴퓨터, False이면 아직 방문하지 않은 컴퓨터
int map[101][101];	// 컴퓨터 사이의 관계

int main() {
	int n, networks;
	cin >> n >> networks;

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

	queue<int> q;
	q.push(1);
	visit[1] = true;
	int cnt = 0;
	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		// 바이러스로 부터 감염된 컴퓨터와 연결된 컴퓨터 확인
		for (int i = 1; i <= n; i++) {
			// 아직 방문하지 않은 컴퓨터
			if (map[tmp][i] == 1 && !visit[i]) {
				visit[i] = true;
				q.push(i);
				cnt++;
			}
		}
	}
	cout << cnt;
}