백준 - 2606 바이러스

 

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

2606번: 바이러스

 

1. 문제 풀이 아이디어

bfs를 이용해 풀었다. 

 

2. 풀이 코드(C++)

 

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#define max 101
using namespace std;
bool visited[max];
vector <int> graph[max];

void bfs(int started) {
	int cnt = 0;//웜 바이러스에 걸린 컴퓨터의 수 저장
	queue<int> q;
	q.push(started);
	visited[started] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i];
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
				cnt++;
			}
		}
	}
	printf("%d", cnt);
}

int main(void) {
	int com = 0;
	int connected = 0;
	scanf("%d %d", &com, &connected);

	for (int i = 0; i < connected; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	bfs(1);
}

 

3. 배운점

컴퓨터는 100대 이하라고 했으니 max를 101로 해야한다.