[C/C++] 코드업(codeup) 4503번 바이러스

▽문제 바로가기

https://codeup.kr/problem.php?id=4503

바이러스

---

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.

둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.

이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

문제 풀이

 

전형적인 BFS 문제입니다. 각 노드도 1부터 차례대로 번호가 매겨져서 풀기가 매우 쉬웠습니다.

---

▽너비 우선 탐색(BFS) 바로가기

https://swblossom.tistory.com/49

[C/C++] 너비 우선 탐색(BFS)

---

1번 컴퓨터가 웜 바이러스에 걸렸을 때 바이러스에 걸리는 컴퓨터의 수를 출력하는 문제입니다.

따라서 큐에 1을 먼저 넣고 시작하면 됩니다.

 

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

vector <int> v[101];
bool check[101] = {false,};
int cnt = -1;	//1번 컴퓨터는 제외하므로

void bfs(){
	queue <int> q;
	q.push(1);	//1번 컴퓨터 감염
	check[1] = true;
	
	while(!q.empty()){
		int now = q.front();
		q.pop();
		cnt++;
		
		//연결된 컴퓨터를 큐에 추가
		for(int i=0;i<v[now].size();++i){
			int x = v[now][i];
			if(!check[x]){
				q.push(x);
				check[x] = true;
			}
		}
		
	}
}

int main(){
	
	int n, m; 
	scanf("%d", &n);
	scanf("%d", &m);
	
	int a, b;
	for(int i=0;i<m;i++){
		scanf("%d %d", &a, &b);
		//각 컴퓨터를 서로 연결
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	bfs();
	
	printf("%d", cnt);
	
	return 0;
}