Node.js) 백준 21609번: 상어 중학교

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

21609번: 상어 중학교

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 dx = [0, 0, -1, 1];
const dy = [1, -1, 0, 0];

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.trim().split(' ').map(Number));

const [N, M] = input.shift();
let board = input;
let answer = 0;
while (true) {
	const target = {
		cnt: -1,
		rainbow: -1,
		baseBlock: [Infinity, Infinity],
	};

	let visited = Array.from(Array(N), () => Array(N).fill(false));

	for (let i = 0; i < N; i++) {
		for (let j = 0; j < N; j++) {
			if (!visited[i][j] && board[i][j] > 0) {
				const q = new Queue();
				let visitedRainbow = Array.from(Array(N), () => Array(N).fill(false));
				visited[i][j] = true;
				const baseBlock = [i, j];
				const color = board[i][j];
				let cnt = 1;
				let rainbow = 0;
				q.push([i, j]);
				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 >= N || ny >= N || visited[nx][ny]) continue;

						// 무지개 블록인 경우
						if (board[nx][ny] == 0 && !visitedRainbow[nx][ny]) {
							visitedRainbow[nx][ny] = true;
							rainbow++;
							cnt++;
							q.push([nx, ny]);
						} else if (board[nx][ny] == color) {
							cnt++;
							visited[nx][ny] = true;
							q.push([nx, ny]);
						}
					}
				}
				if (cnt >= 2) {
					if (cnt > target.cnt) {
						target.cnt = cnt;
						target.rainbow = rainbow;
						target.baseBlock = baseBlock;
					} else if (cnt == target.cnt) {
						if (rainbow > target.rainbow) {
							target.cnt = cnt;
							target.rainbow = rainbow;
							target.baseBlock = baseBlock;
						} else if (rainbow == target.rainbow) {
							if (baseBlock[0] > target.baseBlock[0]) {
								target.cnt = cnt;
								target.rainbow = rainbow;
								target.baseBlock = baseBlock;
							} else if (baseBlock[0] == target.baseBlock[0]) {
								if (baseBlock[1] > target.baseBlock[1]) {
									target.cnt = cnt;
									target.rainbow = rainbow;
									target.baseBlock = baseBlock;
								}
							}
						}
					}
				}
			}
		}
	}

	// 블록 그룹 없으면 종료
	if (target.cnt == -1) break;

	// 블록제거
	const destroyQ = new Queue();
	destroyQ.push([target.baseBlock[0], target.baseBlock[1]]);

	const color = board[target.baseBlock[0]][target.baseBlock[1]];
	board[target.baseBlock[0]][target.baseBlock[1]] = null;
	while (destroyQ.length > 0) {
		const [x, y] = destroyQ.pop();
		for (let k = 0; k < 4; k++) {
			const nx = x + dx[k];
			const ny = y + dy[k];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N || board[nx][ny] == null) continue;
			if (board[nx][ny] == color || board[nx][ny] == 0) {
				board[nx][ny] = null;
				destroyQ.push([nx, ny]);
			}
		}
	}

	//점수 추가
	answer += Math.pow(target.cnt, 2);

	// 중력 작용
	let newBoard = Array.from(Array(N), () => Array(N).fill(null));

	for (let j = 0; j < N; j++) {
		let gravityArr = [];
		for (let i = 0; i < N; i++) {
			if (board[i][j] > -1 && board[i][j] != null) {
				gravityArr.push(board[i][j]);
			} else if (board[i][j] == -1) {
				let k = i - 1;
				while (gravityArr.length > 0) {
					newBoard[k][j] = gravityArr.pop();
					k--;
				}
				newBoard[i][j] = -1;
			}
		}
		let l = N - 1;
		while (gravityArr.length > 0) {
			newBoard[l][j] = gravityArr.pop();
			l--;
		}
	}
	board = newBoard;

	// 반시계 회전
	newBoard = Array.from(Array(N), () => Array(N).fill(null));
	for (let i = 0; i < N; i++) {
		for (let j = 0; j < N; j++) {
			newBoard[N - j - 1][i] = board[i][j];
		}
	}
	board = newBoard;
	newBoard = Array.from(Array(N), () => Array(N).fill(null));

	for (let j = 0; j < N; j++) {
		let gravityArr = [];
		for (let i = 0; i < N; i++) {
			if (board[i][j] > -1 && board[i][j] != null) {
				gravityArr.push(board[i][j]);
			} else if (board[i][j] == -1) {
				let k = i - 1;
				while (gravityArr.length > 0) {
					newBoard[k][j] = gravityArr.pop();
					k--;
				}
				newBoard[i][j] = -1;
			}
		}
		let l = N - 1;
		while (gravityArr.length > 0) {
			newBoard[l][j] = gravityArr.pop();
			l--;
		}
	}
	board = newBoard;
}
console.log(answer);