const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const combinations = function* (elements, selectNumber) {
for (let i = 0; i < elements.length; i++) {
if (selectNumber === 1) {
yield [elements[i]];
} else {
const fixed = elements[i];
const rest = combinations(elements.slice(i + 1), selectNumber - 1);
for (const a of rest) {
yield [fixed, ...a];
}
}
}
};
const sol = (input) => {
const [row, column] = input.shift().split(" ").map(Number);
let table = input.map((e) => e.split(" ").map(Number));
const dist = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let answer = Number.MIN_SAFE_INTEGER;
// 0의 좌표들을 저장
const zeroSpace = [];
for (let i = 0; i < row; i++) {
for (let j = 0; j < column; j++) {
if (table[i][j] === 0) {
zeroSpace.push([i, j]);
}
}
}
// 0의 좌표들로 3가지를 뽑는 조합
for (let arr of combinations(zeroSpace, 3)) {
table = input.map((e) => e.split(" ").map(Number)); // table 초기화
for (let [x, y] of arr) {
table[x][y] = 1;
}
// bfs 실행
const queue = [];
for (let i = 0; i < row; i++) {
for (let j = 0; j < column; j++) {
if (table[i][j] === 2) {
queue.push([i, j]);
}
}
}
while (queue.length) {
let [x, y] = queue.shift();
for (let i = 0; i < 4; i++) {
const nx = x + dist[i][0];
const ny = y + dist[i][1];
if (nx < 0 || ny < 0 || nx >= row || ny >= column) continue;
if (table[nx][ny] === 0) {
table[nx][ny] = 2;
queue.push([nx, ny]);
}
}
}
// bfs 실행 후 0의 수를 카운트
let cnt = 0;
for (let i = 0; i < row; i++) {
for (let j = 0; j < column; j++) {
if (table[i][j] === 0) {
cnt++;
}
}
}
// 2차원 배열에서 특정 원소를 찾는 방법.
// let cnt = [].concat(...table).filter((e) => !e).length;
// 정답을 갱신
answer = Math.max(answer, cnt);
}
return answer;
};
console.log(sol(input));
벽을 세워야하는 조건이 따로 없기 때문에 모든 경우를 찾아줘야 한다. 벽을 3개씩 세워가며 bfs를 해줘야한다.