[알고리즘] 백준 14502 연구소 (JS)

요구사항

1. 벽을 3개 세워서 안전구역이 가장 많은 경우의 안전구역 수를 구하라.

내풀이

일단 무식하게 생각했따 벽을 3개 세우는 경우니까
for문 3개로 벽 3개를 세우고 -> 바이러스를 퍼트리고(dfs, bfs) -> 안전구역 개수 세기
이런 식으로 하다가 막혀서 결국 답을 봤다 C++로 된 답이였는데
그걸 보고 내가 JS도 변환하였다.

let visited;
function solve(n, m, arr, startPoint) {
  let cnt;
  visited = Array.from(new Array(n), () => new Array(m).fill(0));
  startPoint.map((item) => {
    visited[item[0]][item[1]] = 1;
    dfs(n, m, item[0], item[1], arr);
  });
  cnt = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (arr[i][j] == 0 && visited[i][j] == 0) cnt++;
    }
  }
  return cnt;
}
function dfs(n, m, x, y, arr) {
  let dy = [-1, 0, 1, 0];
  let dx = [0, 1, 0, -1];
  for (let i = 0; i < 4; i++) {
    let ny = y + dy[i];
    let nx = x + dx[i];
    if (ny < 0 || nx < 0 || nx >= n || ny >= m) continue;
    if (visited[nx][ny] || arr[nx][ny] == 1) continue;
    visited[nx][ny] = 1;
    dfs(n, m, nx, ny, arr);
  }
  return visited;
}
function solution(n, m, nums) {
  let ret = 0;
  let wall = [];
  let birus = [];
  let copy_nums = Array.from(new Array(n), () => new Array(m).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (nums[i][j] === 0) {
        wall.push([i, j]);
      } else if (nums[i][j] === 2) {
        birus.push([i, j]);
      }
      copy_nums[i][j] = nums[i][j];
    }
  }
  console.log(birus);
  console.log(wall);
  console.log(copy_nums);
  for (let i = 0; i < wall.length; i++) {
    for (let j = 0; j < i; j++) {
      for (let k = 0; k < j; k++) {
        copy_nums[wall[i][0]][wall[i][1]] = 1;
        copy_nums[wall[j][0]][wall[j][1]] = 1;
        copy_nums[wall[k][0]][wall[k][1]] = 1;
        ret = Math.max(ret, solve(n, m, copy_nums, birus));
        copy_nums[wall[i][0]][wall[i][1]] = 0;
        copy_nums[wall[j][0]][wall[j][1]] = 0;
        copy_nums[wall[k][0]][wall[k][1]] = 0;
      }
    }
  }
  console.log(`최종결과 : ${ret}`);
}

const nums = [
  [0, 0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0, 2],
  [1, 1, 1, 0, 0, 2],
  [0, 0, 0, 0, 0, 2],
];
solution(4, 6, nums);