[Javascript][BOJ] 2667 단지번호 붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

핵심 아이디어

dfs/bfs 방식으로 풀 수 있는 문제이고 입력 크기가 작기에 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 direction = [
		[-1, 0],
		[1, 0],
		[0, -1],
		[0, 1],
	]; // 상하좌우
	const visited = [];
	const housePoint = [];
	const board = input.map((string, rowIdx) => {
		const row = Array.from(string).map((str) => parseInt(str));
		row.forEach((elem, colIdx) => {
			if (elem === 1) {
				housePoint.push([rowIdx, colIdx]);
			}
		});
		visited.push(new Array(n + 1).fill(0));
		return row;
	});

	const checkValidPoint = (x, y) => {
		if ((x >= 0) & (y >= 0) && x < n && y < n) {
			return true;
		}
		return false;
	};

	const dfs = (x, y) => {
		for (const [a, b] of direction) {
			if (checkValidPoint(x + a, y + b) && !visited[x + a][y + b]) {
				if (board[x + a][y + b] === 1) {
					visited[x + a][y + b] = 1;
					cnt++;
					dfs(x + a, y + b);
				}
			}
		}
	};

	const ans = [];
	let cnt = 0;

	while (housePoint.length > 0) {
		const [x, y] = housePoint.shift();
		cnt = 0;
		if (!visited[x][y]) {
            visited[x][y] = 1;
            cnt++;
			dfs(x, y);
		}
		if (cnt > 0) ans.push(cnt);
	}
	ans.sort((a, b) => a - b);
	console.log(ans.length);
	if (ans.length > 0) {
		console.log(ans.join('\n'));
	}
};
const input = [];
rl.on('line', function (line) {
	input.push(line);
}).on('close', function () {
	solution(input);
	process.exit();
});