[Node.js] Level 3_발전기

문제

https://level.goorm.io/exam/195694/%EB%B0%9C%EC%A0%84%EA%B8%B0/quiz/1

구름LEVEL

 

풀이

해당 문제는 그래프 탐색 문제이며 각 집이 연결되어있는지 확인하는 문제이다.

 

어떻게 보면 DFS 로 풀면 될거 같지만, DFS로 풀이를 진행하면 각 노드에서 재귀적으로 4방향씩 호출되어 시간초과 오류를 만날 수도 있다....

 

코드

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let n = null;
let input = [];
let answer = 0;
const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];

rl.on('line', (line) => {
	if(n === null) n = +line;
	else if(input.length < n) input.push(line.split(' ').map(Number));
	
	if(input.length === n){
		rl.close();
	}
});

rl.on('close', () => {
	const temp = Array.from({length: n}, () => Array(n).fill(false));
	
	for(let i = 0; i < n; i++){
		for(let j = 0; j < n; j++){
			if(input[i][j] === 0 || temp[i][j]) continue;
			answer += 1;
			temp[i][j] = true;
			const que = [[i, j]];
			
			while(que.length){
				const [x, y] = que.shift();
				
				for(let k = 0; k < 4; k++){
					const nx = x + dir[k][0];
					const ny = y + dir[k][1];
					
					if(nx >= 0 && nx < n && ny >= 0 && ny < n && input[nx][ny] === 1 && temp[nx][ny] === false){
						que.push([nx, ny]);
						temp[nx][ny] = true;
					}
				}
			}
		}
	}
	console.log(answer);
	process.exit();
})