Node.js) 백준 18808번: 스티커 붙이기

https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N, M, K] = input.shift();
let board = Array.from(Array(N), () => Array(M).fill(0));
let stickers = Array.from(Array(K), () => []);
for (let k = 0; k < K; k++) {
	const [r] = input.shift();
	for (let x = 0; x < r; x++) {
		stickers[k].push(input.shift());
	}

	stickers[k] = [...rotate(stickers[k])];
}

function rotate(sticker) {
	const result = [sticker];

	for (let i = 1; i <= 3; i++) {
		const prev = result[i - 1];
		const r = prev.length;
		const c = prev[0].length;
		let rotateSticker = Array.from(Array(c), () => Array(r).fill(0));
		for (let i = 0; i < r; i++) {
			for (let j = 0; j < c; j++) {
				rotateSticker[j][r - i - 1] = prev[i][j];
			}
		}
		result.push(rotateSticker);
	}
	return result;
}

for (let s = 0; s < stickers.length; s++) {
	const sticker = stickers[s];

	for (let k = 0; k < 4; k++) {
		const didPutOn = tryPut(sticker[k]);
		if (didPutOn) break;
	}
}

console.log(
	board.flat().reduce((r, v) => {
		r = r + v;
		return r;
	}, 0)
);

function tryPut(sticker) {
	const r = sticker.length;
	const c = sticker[0].length;

	for (let i = 0; i <= N - r; i++) {
		for (let j = 0; j <= M - c; j++) {
			let possible = true;
			for (let x = 0; x < r; x++) {
				for (let y = 0; y < c; y++) {
					if (sticker[x][y] == 0) continue;
					if (board[i + x][j + y] == 1) {
						possible = false;
						break;
					}
				}
				if (!possible) break;
			}

			if (possible) {
				for (let x = 0; x < r; x++) {
					for (let y = 0; y < c; y++) {
						if (sticker[x][y] == 1) board[i + x][j + y] = 1;
					}
				}
				return true;
			}
		}
	}
	return false;
}