2606) 바이러스 (C++)

 출처 

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

2606번: 바이러스

 내 풀이 

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

void BFS();

vector<int>computer[101];
bool visited[101];

int computer_total = 0;	//첫번째줄 컴퓨터의 수 
int computer_count = 0; // 두번째줄 컴퓨터 쌍의 개수 
int first_computer = 0, second_computer = 0; // 세번째줄부터 입력받을 컴퓨터 1,2

int main()
{
	cin >> computer_total;
	cin >> computer_count;

	for (int i = 0; i < computer_count; i++)
	{
		cin >> first_computer >> second_computer;
		computer[first_computer].push_back(second_computer);
		computer[second_computer].push_back(first_computer);
	}

	BFS();
}

void BFS()
{
	queue<int>q;
	q.push(1);
	visited[1] = true;
	int result = 0;

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

		for (int i = 0; i < computer[cnt_computer].size(); i++)
		{
			//만일 방문되지 않았으면 방문처리 후 큐에 넣고 result++해줌 
			if (!visited[computer[cnt_computer][i]])
			{
				visited[computer[cnt_computer][i]] = true;
				q.push(computer[cnt_computer][i]);
				result++;
			}
		}
	}

	cout << result;	//결과값 
}

 해설

벡터와 큐를 이용하여 풀었다. 3번째 줄부터 입력받은 변수를 벡터 변수에 넣어준 후 BFS 함수를 선언 후 1번 컴퓨터부터 무조건 시작한다는 걸 이용하여  1을 먼저 큐에 넣고 너비 우선 탐색을 이용하여 방문되는 새로운 노드마다 result를 1씩 더해준 뒤 탐색이 끝나면 정답인 result를 출력해준다. 

 

 새로 안 것 

BFS는 재미있다.