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

 

1) 문제설명

 

백준 Online Judge 2606번 바이러스

백준 Online Judge 2606번 바이러스

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

2606번: 바이러스

 

2) 아이디어

그래프를 만들어 BFS로 탐색하고 노드들을 방문할 때마다 카운트를 세서 방문한 총노드를 구한다.

 

3) 코드

#include<iostream>
#include<queue>

using namespace std;
int graph[101][101]={0,};
int c[101];
queue<int> q;
int cnt = 0;
void bfs(int start, int n) {
	queue<int> q;
	q.push(start); // q에 시작점을 넣어줌
	c[start] = true; // 처음 시작한 곳은 방문했다.
	while (!q.empty()) { // 큐가 빌때까지 반복
		int curr = q.front(); // 밑에서 큐에 넣은 것을 저장
		q.pop(); // 
		cnt++;
		for (int i = 1; i <= n; i++) { 
			if (c[i] == 0 && graph[curr][i] == 1) { // 내가 방문하지 않았고 그래프가 이어져 있다면
				c[i] = 1; // 방문하고 
				q.push(i); // 큐에 넣는다.
			}
		}
	}

}

int main() {

	int m, n, a, b;
	cin >> m >> n;


	
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a, &b);
		graph[a][b] = graph[b][a] = 1;
		
	}
	bfs(1,m);
	printf("%d", cnt - 1);
}