문제 개요

문제: 연구소

분류: 구현, 그래프 이론, 브루투포스 알고리즘, 그래프 탐색, 너비 우선 탐색

난이도: 골드4

문제 풀이

빈 칸의 위치와 초기 바이러스의 위치를 미리 배열로 뽑아두고 각각 조합을 구할 때, BFS로 바이러스를 확산시킬 때 사용한다.

전체적인 풀이 과정은 아래와 같다.

1. 빈 칸 중 3가지를 고르는 조합을 구한다.
2. 고른 위치에 벽을 세우고 BFS를 통해 바이러스를 확산시킨다.
3. 바이러스를 확산시킨 연구소에 대해 안전 영역을 구한다.
4. 현재 정답과 안전 영역을 비교하여 더 큰 값으로 정답을 갱신한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [NM, ...lab] = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = NM.split(" ").map(Number);
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
const virusPos = [];
const emptyPos = [];
const wallPos = new Array(3).fill(-1);
let answer = 0;

/** bfs를 통해 바이러스를 확산시킨다. */
const spread = (lab) => {
  let queue = [];
  let visited = Array.from({ length: lab.length }, () =>
    new Array(lab[0].length).fill(false)
  );

  virusPos.forEach(([y, x]) => {
    queue.push([y, x]);
    visited[y][x] = true;
  });

  while (queue.length > 0) {
    let y = queue[0][0];
    let x = queue[0][1];
    queue.shift();

    for (let i = 0; i < 4; i++) {
      let ny = y + dy[i];
      let nx = x + dx[i];

      if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx]) continue;
      if (lab[ny][nx] === 0) {
        lab[ny][nx] = 2;
        queue.push([ny, nx]);
        visited[ny][nx] = true;
      }
    }
  }

  return lab;
};

/** 안전 영역의 개수를 센다. */
const countSafeArea = (lab) => {
  let result = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (lab[i][j] === 0) result++;
    }
  }
  return result;
};

/** 빈 칸 중 3곳을 골라 벽을 세운다. */
const makeCombinations = (idx, wall) => {
  if (wall === 3) {
    // 새로 카피한 lab에서 해당하는 위치에 벽을 세운다.
    let newLab = lab.map((row) => [...row]);
    for (let i = 0; i < 3; i++) {
      let [y, x] = emptyPos[wallPos[i]];
      newLab[y][x] = 1;
    }
    // 바이러스를 확산시킨다.
    let spreadLab = spread(newLab);
    // 현재 정답과 바이러스를 확산시킨 연구소의 안전 영역 중 더 큰 값으로 정답을 갱신한다.
    answer = Math.max(answer, countSafeArea(spreadLab));
    return;
  }

  // 빈 칸 중에서 벽을 세울 위치를 고른다.
  for (let i = idx; i < emptyPos.length; i++) {
    wallPos[wall] = i;
    makeCombinations(i + 1, wall + 1);
  }
};

const solution = () => {
  lab = lab.map((row) => row.split(" "));

  // 초기 바이러스와 빈 칸의 위치를 배열에 따로 저장한다.
  lab.forEach((row, rowIdx) => {
    row.forEach((item, colIdx) => {
      lab[rowIdx][colIdx] = +item;
      if (+item === 2) virusPos.push([rowIdx, colIdx]);
      else if (+item === 0) emptyPos.push([rowIdx, colIdx]);
    });
  });

  makeCombinations(0, 0);
  console.log(answer);
};

solution();