Jeong in Tech

문제

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

접근

- 완전탐색을 하며 지도에 벽3개를 세울 수 있는 경우를 모두 다 조사해야한다.

- 각 벽3개를 세운 경우를 복사하여, 해당 복사본으로 각 경우의 안전지대 수를 구한다.

- 가장 큰 안전지역의 갯수를 반환한다.

풀이

참조 풀이 - https://velog.io/@ywc8851/%EB%B0%B1%EC%A4%80-14502-%EC%97%B0%EA%B5%AC%EC%86%8C-javascript

const fs = require("fs");

// 문제 링크 : https://www.acmicpc.net/problem/14502
// 제출 시 path : /dev/stdin

const input = fs
  .readFileSync("./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => parseInt(v)));

const [COL, ROW] = input.shift();
const graph = input;

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

let max = Number.MIN_SAFE_INTEGER;

// 각 벽이 설치된 경우의 안전지대 갯수를 구한다.(BFS)
const countSafePlace = (graph) => {
  let cnt = 0;
  const queue = [];

  for (let i = 0; i < COL; i++) {
    for (let j = 0; j < ROW; j++) {
      if (graph[i][j] === 2) queue.push([i, j]);
    }
  }

  while (queue.length) {
    const [virusX, virusY] = queue.shift();

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

      if (nx >= 0 && nx < COL && ny >= 0 && ny < ROW && graph[nx][ny] === 0) {
        graph[nx][ny] = 2;
        queue.push([nx, ny]);
      }
    }
  }

  for (let i = 0; i < COL; i++) {
    for (let j = 0; j < ROW; j++) {
      if (graph[i][j] === 0) cnt++;
    }
  }

  return cnt;
};

const solution = (cnt) => {
  if (cnt === 3) {
    const copy = graph.map((v) => [...v]);
    const num = countSafePlace(copy); // 각 벽이 설치된 경우의 안전지대 갯수를 구한다.(BFS)
    max = max < num ? num : max;
    return;
  }
  for (let i = 0; i < COL; i++) {
    for (let j = 0; j < ROW; j++) {
      if (graph[i][j] === 0) {
        graph[i][j] = 1;
        solution(cnt + 1);
        graph[i][j] = 0;
      }
    }
  }
};

solution(0); // 1.벽3개를 세우는 전체 경우의 수를 구한다.(DFS)

console.log(max);

- DFS + BFS 풀이를 모두 쓰는 식이었다.

- DFS 에서 break 문 return 써서 꼭 해당 재귀 종료해주기.

- copy 꼭 해서 원본 배열 상하지 않도록 해주기.

- 왜 벽을 세울 때는 DFS 를, 바이러스를 퍼뜨릴 때는 BFS 를 사용한 걸까?