[백준] 2468번: 안전 영역 - Node.js (자바스크립트)

1. 문제 ㅡ 2468번: 안전 영역 (난이도: Silver I)

2468번: 안전 영역

2. 풀이 ㅡ Node.js (자바스크립트)

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

const getMaxSafeAreas = input => {
  const N = +input.shift();
  const areas = input.map(row => row.split(' ').map(val => +val));
  // 💡 0 ~ 100 모두 탐색할 필요 없이 입력받은 영역들 중 가장 높은 영역까지만 반복문 돌면 됨 
  const MAX_RAINFALL = Math.max(...areas.flat());
  
  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  const safeAreas = [];

  /**
  * 인접 칸들을 DFS 탐색하며 침수되는지 확인해주는 함수  
  * 탐색 중인 칸 또한 침수되지 않는 경우 checked 상태를 true로 변경하고, 해당 칸을 기준으로 함수 재귀 호출됨 
  */ 
  const checkNearbyAreas = (x, y, rainfall, checked) => {
    dirs.forEach(dir => {
      const [newX, newY] = [x + dir[0], y + dir[1]];

      if (newX >= N || newY >= N || newX < 0 || newY < 0 || checked[newY][newX] || areas[newY][newX] <= rainfall)
        return;

      checked[newY][newX] = true;
      checkNearbyAreas(newX, newY, rainfall, checked);
    });
  };

  /**
  * @rainfall -> 비의 양 (0 ~ MAX_RAINFALL)
  * 이중 for문을 통해 모든 칸을 탐색하며 현재 rainfall 기준 침수되지 않는 칸을 찾아서 @checkNearbyAreas 함수를 호출함
  * 한번 호출될 때마다 안전 영역 수를 safeAreas 배열에 넣어줌
  */
  const countSafeZonesByRainfall = rainfall => {
    const checked = Array.from({ length: N }).map(() => Array.from({ length: N }, () => false));
    let count = 0;

    for (let y = 0; y < N; y++) {
      for (let x = 0; x < N; x++) {
        if (areas[y][x] <= rainfall || checked[y][x]) continue;

        count += 1;
        checkNearbyAreas(x, y, rainfall, checked);
      }
    }

    safeAreas.push(count);
  };

  // 0부터 MAX_RAINFALL까지 비의 양을 올리면서 countSafeZoneByRainfall 함수 호출
  for (let rainfall = 0; rainfall <= MAX_RAINFALL; rainfall++) {
    countSafeZonesByRainfall(rainfall);
  }

  // 마지막에 safeAreas에 들어있는 값 중 가장 큰 값을 반환함 
  return Math.max(...safeAreas);
};

console.log(getMaxSafeAreas(input));

2-1. 풀이 설명

강우량을 0부터 MAX_RAINFALL(영역들 중 가장 높은 영역의 값)까지 증가시키며, 강우량 별 생기는 안전 영역의 수를 구했다. 마지막에 안전 영역의 수 중 최댓값을 반환하는 식으로 문제에 접근했다.

 

• 강우량 별로 모든 영역을 순회하며 침수되지 않는 칸을 찾는다. 이때 침수되지 않은 칸은 현재 강우량보다 높아야 함과 동시에 checked 상태가 false여야 한다. 즉, 이미 확인한 칸은 다시 확인하지 않는다. 
• 침수되지 않는 칸의 좌표를 인수로 checkNearbyAreas 함수를 호출해 인접 칸들의 침수여부를 확인한다. 만약 침수되지 않는 칸이 있으면, 인접 칸의 checked 상태를 true로 바꿔주고 checkNearbyAreas 함수를 재귀적으로 호출한다.
• 강우량 별로 안전 영역의 수를 구했으면, 이를 safeAreas 배열에 저장해두고 다음 강우량으로 이동한다. 
• 모든 반복문이 끝난 후 safeAreas 배열에 저장되어 있는 값 중 최댓값을 반환한다.