[BAEKJOON] 2606번 : 바이러스

문 제

 

소 스  코 드

#include <iostream>
#include <set>
#include <map>
#include <queue>

typedef std::map<int, std::set<int>> Graph;
constexpr int FIRSTVIRUS{ 1 };

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, M;

	std::cin >> N >> M;
	
	Graph computers;
	bool * virus{ new bool[N + 1] };
	std::queue<int> log;

	int fCom, sCom;
	for (int i = 0; i < M; ++i) {
		std::cin >> fCom >> sCom;
		computers[fCom].insert(sCom);
		computers[sCom].insert(fCom);
	}

	// BFS
	std::fill_n(virus, N + 1, false);
	log.push(FIRSTVIRUS);
	virus[FIRSTVIRUS] = true;

	while (!log.empty()) {

		int point{ log.front() };
		log.pop();

		for (const auto& com : computers[point]) {
			if (false == virus[com]) {
				virus[com] = true;
				log.push(com);
			}
		}
	}

	int num{ 0 };
	for (int i = 1; i <= N; ++i) {
		if (true == virus[i]) ++num;
	}
	// 1번 컴퓨터는 바이러스 숙주
	std::cout << num - 1 << '\n';

	delete[] virus;

	return 0;
}

 

풀 이

 

• 1차, 2차 감염으로 생각한다면, BFS(너비 우선 탐색) 입니다.

• 감염된 컴퓨터를 확인 후 갯수를 확인하는 방법을 사용하였습니다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/2606

2606번: 바이러스