Node.js) 백준 16988번: Baaaaaaaaaduk2 (Easy)

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

16988번: Baaaaaaaaaduk2 (Easy)

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().split('\n').map(v => v.split(' ').map(Number));
const [N, M] = input.shift();
const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];

let board = input;
const possible = [];


for (let i = 0; i < N; i++) {
	for (let j = 0; j < M; j++) {
		if (board[i][j] == 0) {
			possible.push([i, j])
		}
	}
}

let max = 0;

for (let n = 0; n < possible.length; n++) {
	for (let m = n + 1; m < possible.length; m++) {
		const [x1, y1] = possible[n];
		const [x2, y2] = possible[m];
		board[x1][y1] = 1;
		board[x2][y2] = 1;
		let visited = Array.from(Array(N), () => Array(M).fill(false));
		let total = 0;


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

							if (board[nx][ny] == 2) {
								visited[nx][ny] = true;
								q.push([nx, ny])
								cnt++;
							} else if (board[nx][ny] == 0) {
								impossible = true;
							}
						}
					}
					if (!impossible) total += cnt;
				}
			}
		}

		if (total > max) {
			max = total;
		}
		board[x1][y1] = 0;
		board[x2][y2] = 0;
	}
}

function check(x, y) {
	for (let k = 0; k < 4; k++) {
		const nx = x + dx[k];
		const ny = y + dy[k];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		if (board[nx][ny] == 0) return false;
	}
	return true;
}

console.log(max)