[백준][Node.js] 2606번 : 바이러스

 

 

Algorithm

-  바이러스 -

 

---

 

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

입출력 예시

 

문제 풀기

const readline = require("readline");
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let input = [];
let computerCount = 0;
let count = 0;
let graph = [];
let visited = [];
let result = [];
rl.on("line", function (line) {
	if (!computerCount) computerCount = Number(line);
	else if (!count) count = Number(line);
	else input.push(line.toString());
}).on("close", function () {
	input = input.map((el) => el.split(" ").map((el) => Number(el)));
	graph = Array.from(Array(computerCount), () => Array(computerCount).fill(0));
	input.forEach((el) => {
		graph[el[0] - 1][el[1] - 1] = 1;
		graph[el[1] - 1][el[0] - 1] = 1;
	});
	visited = new Array(computerCount).fill(false);
	DFS(0);
	console.log(result.length - 1);
	process.exit();
});

let DFS = (num) => {
	visited[num] = true;
	result.push(num);
	for (let i = 0; i < graph.length; i++) {
		if (graph[num][i] && !visited[i]) {
			DFS(i);
		}
	}
	return;
};