[백준 2468 - Node.js] 안전 영역

 

문제 링크

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

2468번: 안전 영역

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input[0];
const areas = input.slice(1).map(v => v.split(' ').map(v => +v));

const offsetX = [0, 0, -1, 1];
const offsetY = [-1, 1, 0, 0];

const dfs = (x, y, height, visited) => {
  offsetX.forEach((dx, i) => {
    const nx = x + dx;
    const ny = y + offsetY[i];
    if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
      visited[nx][ny] = true;
      dfs(nx, ny, height, visited);
    }
  });
};

let maxCount = 0;
for (let height = 0; height <= 100; height++) {
  let count = 0;
  const visited = [...Array(N)].map((_, x) => [...Array(N)].map((_, y) => areas[x][y] <= height));
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (!visited[i][j]) {
        visited[i][j] = true;
        dfs(i, j, height, visited);
        count++;
      }
    }
  }
  maxCount = Math.max(maxCount, count);
}

console.log(maxCount);

비가 왔을 때 잠기는 높이를 0부터 100까지 증가시키면서 안전 영역의 개수의 최댓값을 찾으면 된다.

 

아래 3중 for문에서 가장 바깥쪽 for문에서 비가 왔을 때 잠기는 높이를 0부터 100까지 증가시킨다.

높이를 변경시킬 때마다 visited를 새로 갱신하는데, 이 때 잠기는 지역은 true로 설정하여 이미 방문한 것으로 처리한다. 이렇게 하면 DFS를 할 때 1. 물에 잠기지 않았고 2. 아직 방문하지 않은 지역을 한 번에 판단할 수 있다.

 

안쪽의 2중 for문에서 모든 지역을 순회하면서 1. 물에 잠기지 않았고 2. 아직 방문하지 않은 지역에서 방문 여부를 갱신한 후 DFS를 실행한다. DFS를 할 때 상하좌우 4방향 중 갈 수 있는 지역(물에 잠기지 않고 방문하지 않은 지역)으로 재귀적으로 DFS를 실행하여 맨 처음 DFS를 실행한 지역으로부터 갈 수 있는 모든 지역을 다 방문하게 된다.

모든 방문을 마치고 나면 DFS가 종료되고 count를 1 증가시킨다.

 

모든 지역을 한 번 순회하여 DFS를 각각 실행한 후의 count의 최댓값을 maxCount에 계속 갱신한다.

이 과정을 모든 높이에 대해 실행하여 maxCount의 최댓값을 출력하였다.