Node.js) 백준 20058번: 마법사 상어와 파이어스톰

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

20058번: 마법사 상어와 파이어스톰

class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.length = 0;
	}

	push(item) {
		const node = new Node(item);
		if (this.head == null) {
			this.head = node;
		} else {
			this.tail.next = node;
		}

		this.tail = node;
		this.length += 1;
	}

	pop() {
		const popItem = this.head;
		this.head = this.head.next;
		this.length -= 1;
		return popItem.item;
	}
}

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N, Q] = input.shift();
const W = Math.pow(2, N);

let board = [];
for (let i = 0; i < W; i++) {
	board.push(input.shift());
}
const L = input.shift();

const dx = [0, 0, 1, -1];
const dy = [-1, 1, 0, 0];

L.forEach((l) => {
	const d = Math.pow(2, l);
	let newBoard = Array.from(Array(W), () => Array(W));
	// 돌리고
	for (let r = 0; r < W; r += d) {
		for (let c = 0; c < W; c += d) {
			for (let i = 0; i < d; i++) {
				for (let j = 0; j < d; j++) {
					newBoard[j + r][d - 1 - i + c] = board[i + r][j + c];
				}
			}
		}
	}

	// console.log(newBoard.map((v) => v.join(' ')).join('\n'));

	//녹이고
	for (let x = 0; x < W; x++) {
		for (let y = 0; y < W; y++) {
			let cnt = 0;
			for (let k = 0; k < 4; k++) {
				const nx = x + dx[k];
				const ny = y + dy[k];
				if (nx < 0 || ny < 0 || nx >= W || ny >= W) continue;
				if (newBoard[nx][ny] > 0) cnt++;
			}
			if (cnt < 3 && newBoard[x][y] > 0) {
				board[x][y] = newBoard[x][y] - 1;
			} else {
				board[x][y] = newBoard[x][y];
			}
		}
	}
});

// console.log(board.map((v) => v.join(' ')).join('\n'));
let total = 0;
let widest = 0;
let visited = Array.from(Array(W), () => Array(W).fill(false));
for (let i = 0; i < W; i++) {
	for (let j = 0; j < W; j++) {
		total += board[i][j];
		if (!visited[i][j] && board[i][j] > 0) {
			let area = 1;
			const q = new Queue();
			q.push([i, j]);
			visited[i][j] = true;
			while (q.length > 0) {
				const [x, y] = q.pop();
				for (let k = 0; k < 4; k++) {
					const nx = x + dx[k];
					const ny = y + dy[k];
					if (
						nx < 0 ||
						ny < 0 ||
						nx >= W ||
						ny >= W ||
						board[nx][ny] == 0 ||
						visited[nx][ny]
					)
						continue;
					area += 1;
					visited[nx][ny] = true;
					q.push([nx, ny]);
				}
			}
			widest = Math.max(widest, area);
		}
	}
}

console.log(total);
console.log(widest);