[백준] 14502 연구소 - javascript

📌 문제

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

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const [col, row] = input.shift().split(' ').map(Number);
const board = input.map((i) => i.split(' ').map(Number));
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
let ans = 0;

const countingSafeZone = (arr) => {
  let cnt = 0;
  let queue = [];

  for (let i = 0; i < col; i++) {
    for (let j = 0; j < row; j++) {
      if (arr[i][j] === 2) queue.push([i, j]);
    }
  }

  while (queue.length) {
    const [curX, curY] = queue.shift();

    for (let i = 0; i < 4; i++) {
      const [nx, ny] = [curX + dx[i], curY + dy[i]];

      if (nx >= 0 && nx < col && ny >= 0 && ny < row && arr[nx][ny] === 0) {
        arr[nx][ny] = 2;
        queue.push([nx, ny]);
      }
    }
  }

  for (let i = 0; i < col; i++) {
    for (let j = 0; j < row; j++) {
      if (arr[i][j] === 0) {
        cnt += 1;
      }
    }
  }

  return cnt;
};

const dfs = (cnt) => {
  if (cnt === 3) {
    let arr = board.map((v) => [...v]);
    let cntOfSafe = countingSafeZone(arr);

    ans = Math.max(ans, cntOfSafe);
    return;
  }

  for (let i = 0; i < col; i++) {
    for (let j = 0; j < row; j++) {
      if (board[i][j] === 0) {
        board[i][j] = 1;
        dfs(cnt + 1);
        board[i][j] = 0;
      }
    }
  }
};

dfs(0);
console.log(ans);

✔ 알고리즘 : BFS / DFS + 구현

✔ 내가 풀이한 방법
벽3개 설치 👉 벽개수가 3개가 되었을 때 바이러스 퍼뜨리기 👉 안전영역 개수 카운팅

1. 백트래킹으로 벽 3개 설치 (DFS)

for (let i = 0; i < col; i++) {
  for (let j = 0; j < row; j++) {
    if (board[i][j] === 0) {
      board[i][j] = 1;
      dfs(cnt + 1);
      board[i][j] = 0;
    }
  }
}

2. 벽개수 3개 되었을 때 바이러스 퍼뜨리기 (BFS)

let cnt = 0;
let queue = [];

for (let i = 0; i < col; i++) {
  for (let j = 0; j < row; j++) {
    if (arr[i][j] === 2) queue.push([i, j]);
  }
}

while (queue.length) {
  const [curX, curY] = queue.shift();

  for (let i = 0; i < 4; i++) {
    const [nx, ny] = [curX + dx[i], curY + dy[i]];

    if (nx >= 0 && nx < col && ny >= 0 && ny < row && arr[nx][ny] === 0) {
      arr[nx][ny] = 2;
      queue.push([nx, ny]);
    }
  }
}

❗ 2차원배열을 깊은복사하여 넘겨줘야 원본배열(board)가 변하지 않는다

// 깊은복사로 배열전달
if (cnt === 3) {
  let arr = board.map((v) => [...v]);
  let cntOfSafe = countingSafeZone(arr);

  ans = Math.max(ans, cntOfSafe);
  return;
}

3. 안전영역 개수 카운팅

for (let i = 0; i < col; i++) {
  for (let j = 0; j < row; j++) {
    if (arr[i][j] === 0) {
      cnt += 1;
    }
  }
}

return cnt;

✔ 난이도 : 백준 기준 골드 5