C++ 알고리즘 문제 풀이(BFS)

백준 2606 문제 바이러스

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

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

 

 

문제 해결 방법: BFS
각노드들을 순차적으로 몇번 왔다갔다 하는지 만 보면 된다.최단거리 사용에 유용하나 이 문제에 적용가능

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

//첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 
//이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

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

int coumputer_num; // <= 100
int E; // 네트워크상 직접 연결되어있는 쌍의 수 
using namespace std;
vector <int> a[101];
bool checked[101];

int bfs(int start)
{
	int solution = -1;
	queue<int> q;
	
	q.push(start);

		
	while (!q.empty())
	{
		int x = q.front();

		q.pop();

		for (int i = 0; i<a[x].size() ; i++) //
		{
			sort(a[x].begin(), a[x].end());
			if (checked[a[x][i]] != true)
			{
				q.push(a[x][i]);
				checked[a[x][i]] = true;
				solution++;
			}

		}
	}

	return solution;
}


int main(void)
{
	int count = 0;
	int temp1; //인접행렬 나타내기위한 도구
	int temp2; //인접행렬 나타내기위한 도구
	cin >> coumputer_num;
	cin >> E;

	for (int i = 0;i < E;i++)
	{
		cin >> temp1;
		cin >> temp2;
		a[temp1].push_back(temp2);
		a[temp2].push_back(temp1);

	}

	count = bfs(1);
	printf("%d", count);
	return 0;
}