백준 14502 < 연구소 > JavaScript

📍문제 링크

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

14502번: 연구소

 

📍알고리즘 분류

- 구현
- 그래프 이론
- 브루트포스 알고리즘
- 그래프 탐색
- 너비 우선 탐색

 

📍문제 풀이

- N(세로) * M(가로) 좌표 평면에 바이러스, 벽, 빈칸이 존재한다. 벽을 딱 3개만 세울 수 있을 때, 확보 가능한 안전영역의 최대넓이를 구하라

- 바이러스는 벽이 없는 상하좌우로 퍼질 수 있다

 

예시

- 빨간 2 = 바이러스 좌표

- 파란 1 = 벽

- 초록 0 = 벽을 세우는 좌표 (3개만 존재)

- 오렌지 0 = 바이러스 확산 (최소화해야함

 

브루트포스 카테고리가 붙은것을 보니, N * M 좌표 평면에서 빈칸 3개를 조합해 벽을 세워보고 안전 영역의 최대값을 구하는 방식으로 해결할 수 있을 것 같다

 

✅문제 풀이 과정

1. 좌표 평면에서 0인 좌표중 3개를 골라서 벽을 세운다  (백트래킹으로 조합 구현)

1-1. 벽 3개를 세운 뒤 바이러스를 확산한다 (DFS)

1-2. 안전 영역의 갯수를 센다 (중첩 for 문으로 완전 탐색)

1-3. 안전 영역의 갯수의 최댓값을 갱신한다

 

2. 반복이 끝나고 안전 영역의 갯수의 최댓값을 리턴한다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
// 상하좌우 순서
const dys = [-1, 1, 0, 0];
const dxs = [0, 0, -1, 1];
let maxSafeArea = 0;

// 바이러스 좌표를 받아서 바이러스를 확산하는 DFS 함수
const spread = (map, y, x) => {
  const stack = [[y, x]];
  while (stack.length) {
    const [Y, X] = stack.pop();

    for (let i = 0; i < 4; i++) {
      const [newY, newX] = [Y + dys[i], X + dxs[i]];
      if (
        newY >= 0 &&
        newY < map.length &&
        newX >= 0 &&
        newX < map[0].length &&
        map[newY][newX] === 0
      ) {
        stack.push([newY, newX]);
        map[newY][newX] = 2;
      }
    }
  }
};

// 백트래킹으로 벽 3개 세우는 함수
const recursive = (map, depth) => {
  if (depth === 3) {
    // 0인 좌표 3개를 1로 만든 상태
    // 여기서 바이러스 확산 실행
    const virusPosArr = getVirusPos(map);
    const newMap = map.map((row) => [...row]); // deepcopy
    virusPosArr.forEach((pos) => spread(newMap, ...pos));
    maxSafeArea = Math.max(maxSafeArea, countSafeArea(newMap));
    return;
  }

  for (let i = 0; i < map.length; i++) {
    for (let j = 0; j < map[0].length; j++) {
      if (map[i][j] === 0) {
        map[i][j] = 1;
        recursive(map, depth + 1);
        map[i][j] = 0;
      }
    }
  }
};

// 바이러스 좌표들을 배열로 리턴해주는 함수
const getVirusPos = (map) => {
  const posList = [];
  for (let i = 0; i < map.length; i++) {
    for (let j = 0; j < map[0].length; j++) {
      if (map[i][j] === 2) posList.push([i, j]);
    }
  }
  return posList;
};

// 안전 영역 카운트해주는 함수
const countSafeArea = (map) => {
  let safeArea = 0;
  for (let i = 0; i < map.length; i++) {
    for (let j = 0; j < map[0].length; j++) {
      if (map[i][j] === 0) safeArea++;
    }
  }
  return safeArea;
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  input.shift();
  const board = input.map((row) => row.split(" ").map(Number));
  recursive(board, 0);
  console.log(maxSafeArea);
});

 

📍리뷰

- 안전영역을 중첩 for 문으로 찾아줬지만, DFS나 BFS를 사용하면 시간 복잡도를 더 줄일 수 있을 것 같다