[백준 14502번] DFS(깊이 우선 탐색) - 연구소

✨ 문제 ✨

✨ 정답 ✨

const { notDeepEqual } = require("assert");
const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim().split('\n');


// const fs = require('fs'); 
// let input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

const [N, M] = input.shift().split(' ').map((el) => +el);
let originalArray = [];
input.map((el) => originalArray.push(el.split(' ').map((el2) => +el2)))

const dx = [-1, 0, 1, 0];
const dy = [0, -1, 0, 1];

let max = 0;

// 안전 영역 세기(벽이 3개가 되면 사용)
const countSafeArea = (array) => {
  let safe = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (array[i][j] === 0) {
        safe += 1;
      }
    }
  }
  return safe;
}


// 벽 세우기
const wall = (boardArray, wallCount) => {
  if (wallCount === 3) {
    // 바이러스 퍼뜨리기
    let virusIs = []
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (boardArray[i][j] === 2) {
          virusIs.push([i, j]);
        }
      }
    }
    let newBoardArray = boardArray.map((el) => [...el]);
    virusIs.forEach((pos) => DFS(newBoardArray, ...pos));
    // 새로운 지도로 안전 영역 세기
 
    max = Math.max(max, countSafeArea(newBoardArray));
    return;


  }
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (boardArray[i][j] === 0) {
        boardArray[i][j] = 1;
        wall(boardArray, wallCount + 1);
        boardArray[i][j] = 0; // *** 여기 다시 되돌려놔야 함.
      }
    }
  }
}


// 벽 다 세우면 바이러스 퍼뜨리기(DFS);
const DFS = (boardArray, y, x) => {
  let queue = [[y, x]];
  while (queue.length > 0) {
    const [currentY, currentX] = queue.pop();
    for (let i = 0; i < 4; i++) {
      let nextY = currentY + dy[i];
      let nextX = currentX + dx[i];
      // *********M을 N으로 써서 틀렸었다.
      if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M
        && boardArray[nextY][nextX] === 0) {
        queue.push([nextY, nextX]);
        boardArray[nextY][nextX] = 2;
      }
    }
  }
}

wall(originalArray, 0)
console.log(max)

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡