[Javascript][BOJ] 2606 바이러스 (dfs)

www.acmicpc.net/problem/2606

2606번: 바이러스

 

핵심아이디어

전형적인 DFS문제라서 딱히 언급할 것이 없다.

연결된 모든간선에 대해 dfs를 수행하되, 방문처리를 한 노드는 방문하지 않으면 된다.

 

'use strict';

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

const solution = function (input) {
	const n = parseInt(input.shift());
	const m = parseInt(input.shift());
	const graph = [...new Array(n + 1)].map(() => []);
	const visited = [...new Array(n + 1)].fill(0);
	let cnt = 0;

	for (const edge of input) {
		const [start, dest] = edge.split(' ').map((elem) => parseInt(elem));
		graph[start].push(dest);
		graph[dest].push(start);
	}
	visited[1] = 1;

	const dfs = (start) => {
		for (const dest of graph[start]) {
			if (!visited[dest]) {
				visited[dest] = 1;
				cnt++;
				dfs(dest);
			}
		}
	};

	dfs(1);
	console.log(cnt);
};

const input = [];
rl.on('line', function (line) {
	input.push(line);
}).on('close', function () {
	solution(input);
	process.exit();
});