[백준2468_자바스크립트(javascript)] - 안전 영역

🔴 문제

안전 영역

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [head, ...input] = fs.readFileSync(path).toString().trim().split('\r\n');
const n = Number(head);
const area = input.map((it) => it.split(' ').map((it) => Number(it)));
let visited;
let answer = 0;

let max = 0;
let min = 100;

function dfs(x, y, h) {
  if (x < 0 || y < 0 || x >= n || y >= n) return false;
  if (visited[x][y] === true) return false;
  if (area[x][y] < h) {
    visited[x][y] = true;

    return false;
  } else {
    visited[x][y] = true;
    dfs(x + 1, y, h);
    dfs(x - 1, y, h);
    dfs(x, y + 1, h);
    dfs(x, y - 1, h);

    return true;
  }
}

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (area[i][j] > max) max = area[i][j];
    if (area[i][j] < min) min = area[i][j];
  }
}

for (let h = min; h <= max; h++) {
  visited = Array.from({ length: n }, () => Array(n).fill(false));

  let cnt = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(i, j, h)) {
        cnt += 1;
      }
    }
  }
  answer = Math.max(answer, cnt);
}

console.log(answer);

🟢 풀이

일단 각 지역 높이의 최소값부터 최대값까지만 확인하면 연산 횟수를 훨씬 줄일 수 있기 때문에 각 지역을 전체 순회하면서 최소값과 최대값을 구해줬다.
그래서 높이가 min일때부터 max일때까지 모든맵을 순회하면서 DFS를 수행해주기 때문에 for의 깊이가 3이다. n이 100 이하이기에 가능한 문제...
아무튼! 배열을 max-min번 돌아줘야 하기 때문에 배열 내부 요소값을 직접 변경하지는 못한다. 따라서 방문여부를 체크하는 visited 배열을 하나 만들어주고 초기화 해준다.
이후 체크할 좌표 값과 확인할 비의 높이 정보까지 같이 전달해서 DFS를 수행해준다.
다른 DFS문제처럼 1. 범위 체크, 2. 방문 여부 체크 를 진행해주고 재귀호출을 진행해주면 되는데 이 때 물에 잠기지 않는 지역만 재귀호출을 진행해준다. 만약 물에 잠기더라도 방문체크는 해줘야 한다. 따라서 3. 높이 확인 까지 진행해준다.

그리고 처음에 아무리봐도 로직은 맞는 것 같은데 원하는 값이 안나오길래 지피티의 도움을 받았다.
문제가 되는 코드는 아래 코드였다.

visited = new Array(n).fill(new Array(n).fill(false));

방문배열을 초기화 해줄 때 위와 같이 초기화 해줬는데 이 때 바깥 배열을 채우고 있는 안쪽 배열이 하나의 배열을 참조하고 있던 것이 문제였다.

따라서 2차원 배열을 초기화 해줄때는 아래와 같이 초기화 해야한다.

visited = Array.from({ length: n }, () => Array(n).fill(false));

🔵 Ref