🎲 백준 2468번 안전 영역

백준 2468번

💊 아무 지역도 물에 잠기지 않을 수도 있으므로 기준 높이를 0부터 해야한다. 기준 높이에 100을 포함시키지 않아도 되는 이유는 기준 높이가 0일때 안전영역의 개수가 1이 보장되기때문!

코드

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

const N = +input.shift();

const arr = input.map((item) => item.split(" ").map(Number));

const dir = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];

const DFS = (checked, y, x, line) => {
  const willCheck = [[y, x]];
  while (willCheck.length) {
    const [y, x] = willCheck.pop();
    checked[y][x] = 1;
    for (let i = 0; i < 4; i++) {
      const nextY = y + dir[i][0];
      const nextX = x + dir[i][1];
      if (
        nextX >= 0 &&
        nextX < N &&
        nextY >= 0 &&
        nextY < N &&
        arr[nextY][nextX] > line &&
        checked[nextY][nextX] === 0
      ) {
        willCheck.push([nextY, nextX]);
      }
    }
  }
};

const result = [];

for (let line = 0; line <= 99; line++) {
  let checked = Array.from(new Array(N), () => new Array(N).fill(0));
  let safe = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (checked[i][j] === 0 && arr[i][j] > line) {
        DFS(checked, i, j, line);
        safe++;
      }
    }
  }
  result.push(safe);
}

console.log(Math.max(...result));