[알고리즘/백준/14502] 연구소(BFS, DFS, Nodejs)

문제

---

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

14502번: 연구소

 

풀이

---

0은 빈 칸, 1은 벽, 2는 바이러스가 있고, 바이러스는 4방향으로 퍼져나갈 수 있다. 

이때 벽을 3개 세운 뒤 바이러스가 퍼질 수 없는 영역인 안전 영역의 최대 크기를 찾는 문제이다. 

 1. 0인 구간 가운데 3개 고르기 (3중 for문 또는 DFS)
 2. 2인 경우 큐에 넣어서 BFS 돌리면서 2로 바꾸고
 3. 전체 탐색하면서 0인 곳 개수 세서 최댓값 찾기
 

이때 주의해야할 점은 3개를 선정하고 BFS를 도는 작업을 반복적으로 하기 때문에 map을 복사해놓고 변경해야 한다는 점이다. 

또 BFS를 돌 때 mapCopy 요소를 변경하면서 돌기 때문에 따로 체크 배열을 사용할 필요가 없다. 

DFS의 경우, count가 3개가 될 때까지(벽이 될 곳을 고름) 2중 for문을 돌면서 [i, j]를 선택하는 방식이다. 

 

다른 사람의 코드를 보면서 2차원 배열 요소의 값을 확인할 때 flat 또는 [].concat(...arr)로 평탄화할 수 있음을 배웠다. 

3중 for문 풀이

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
    this.tail = 0;
  }
  push(item) {
    this.data[this.tail++] = item;
  }
  pop() {
    this.head++;
  }
  front() {
    return this.data[this.head];
  }
  rear() {
    return this.data[this.tail - 1];
  }
  isEmpty() {
    return this.head === this.tail;
  }
  size() {
    return Math.abs(this.head - this.tail);
  }
}
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [input, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input.split(" ").map(Number); // x, y
const map = arr.map((row) => row.split(" ").map(Number));
const zeroNodes = [];
const dir = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (map[i][j] === 0) {
      zeroNodes.push([i, j]);
    }
  }
}

const len = zeroNodes.length;
let maxSize = Number.MIN_SAFE_INTEGER;

for (let i = 0; i < len; i++) {
  for (let j = i + 1; j < len; j++) {
    for (let k = j + 1; k < len; k++) {
      const [[ix, iy], [jx, jy], [kx, ky]] = [
        zeroNodes[i],
        zeroNodes[j],
        zeroNodes[k],
      ];

      map[ix][iy] = 1;
      map[jx][jy] = 1;
      map[kx][ky] = 1;
      BFS();
      map[ix][iy] = 0;
      map[jx][jy] = 0;
      map[kx][ky] = 0;
    }
  }
}

function BFS() {
  let count = 0;
  const queue = new Queue();
  let mapCopy = Array.from({ length: N }, () => Array(M).fill(0));

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      mapCopy[i][j] = map[i][j];
      if (map[i][j] === 2) queue.push([i, j]);
    }
  }

  while (!queue.isEmpty()) {
    const [x, y] = queue.front();
    queue.pop();

    for (let k = 0; k < 4; k++) {
      const nx = x + dir[k][0];
      const ny = y + dir[k][1];

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

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (mapCopy[i][j] === 0) count += 1;
    }
  }

  maxSize = Math.max(maxSize, count);
}

console.log(maxSize);

 

DFS 풀이

const [N, M] = input.split(" ").map(Number); // x, y
const map = arr.map((row) => row.split(" ").map(Number));
const dir = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

let maxSize = Number.MIN_SAFE_INTEGER;

// 3개 뽑기 : DFS(count)
function DFS(count) {
  if (count === 3) {
    const count = BFS();
    maxSize = Math.max(maxSize, count);
  } else {
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (map[i][j] === 0) {
          map[i][j] = 1;
          DFS(count + 1);
          map[i][j] = 0;
        }
      }
    }
  }
}

// 0 개수 세기 : BFS
function BFS() {
  let count = 0;
  const queue = new Queue();
  let mapCopy = Array.from({ length: N }, () => Array(M).fill(0));

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      mapCopy[i][j] = map[i][j]; // copy
      if (map[i][j] === 2) queue.push([i, j]); // queue에 넣기
    }
  }

  while (!queue.isEmpty()) {
    const [x, y] = queue.front();
    queue.pop();

    for (let k = 0; k < 4; k++) {
      const nx = x + dir[k][0];
      const ny = y + dir[k][1];

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

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (mapCopy[i][j] === 0) count += 1;
    }
  }

  return mapCopy.flat().filter((el) => el === 0).length;
}

DFS(0);
console.log(maxSize);