백준 14502 연구소

문제

제한 사항

입출력 예

풀이

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를 해줘야한다.