[백준]2468번 '안전 영역' 문제 풀이 - JavaScript

[백준]2468번 '안전 영역' 문제 풀이 - JavaScript

문제 📖

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

2468번: 안전 영역

풀이 알고리즘: DFS

난이도: 실버 1

접근 방법 ❓

나는 DFS로 문제를 풀이했다.

문제가 요구하는 것은 조건에 맞는 연결 요소가 몇 개인지 찾는 것이다.

빗물에 잠기지 않는 높이의 연결요소를 찾기 때문에 비가 내렸을 때 쌓이는 높이보다 높은 요소들을 찾아주면 된다.

주의 사항으로 "아무 지역도 물에 잠기지 않을 수도 있다."라는 말이 있기 때문에 비가 안 내려서 모두 안 잠기는 상황도 있을 수 있다.

반응형

풀이 코드 💡

const fs = require('fs');
const file = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');

const [n, ...arr] = input;
const graph = arr.map((item) => item.split(' ').map(Number));
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
let maxHeight = 0;
for (const x of graph) {
  maxHeight = Math.max(maxHeight, ...x);
}

function dfs(graph, x, y, target) {
  if (x < 0 || x >= n || y < 0 || y >= n) {
    return false;
  }

  if (graph[x][y] <= target) {
    return false;
  }

  graph[x][y] = 0;
  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];
    dfs(graph, nx, ny, target);
  }

  return true;
}

let answer = 0;
let count = 0;
while (maxHeight > -1) {
  const newGraph = graph.map((item) => [...item]);

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(newGraph, i, j, maxHeight)) {
        count++;
      }
    }
  }

  answer = Math.max(answer, count);
  count = 0;

  maxHeight--;
}

console.log(answer);

풀이 해설 💡

빗물이 쌓여서 잠길 수 있는 최대의 높이는 지역 중 최대의 높이가 될 것이다.

그 이상으로는 계산해도 최대 높이의 값으로 계산했을 때와 같이 나오기 때문에 의미가 없을 것이다.

그래서 maxHeight을 구해주고 maxHeight까지만 반복문이 실행되게 끔 해줬다.

 

while문에서는 최대 높이부터 0까지 반복이 될 수 있도록 해줬다.

최대 높이가 변경 될 때마다 graph를 초기 상태에서 검사해야 하기 때문에 초기상태로 돌려준다.

그리고 왼쪽 상단부터 순차적으로 검사할 수 있도록 이중반복문을 사용하고 dfs함수를 호출한다.

dfs함수는 초기화한 graph와 행(i), 열(j), 비교해서 검사할 최대 높이를 인자로 받는다.

그리고 true값 즉 최대 높이보다 높은 지역을 상,하,좌,우 갈 수 있는 방향을 방문처리 하면서 순회해서 잘 돌아왔다면 count를 해준다.

최종적으로 최대한 물이 안 잠기는 지역을 출력해야 하기 때문에 answer와 count 변수를 비교해서 높이마다 계산한 최대 지역을 answer에 담아주고 다음 높이에 대한 count를 위해 count를 0으로 초기화해준다.

 

dfs함수에서는  그래프의 영역에서 벗어나거나, 재귀를 도는 graph의 요소가 비교하고자 하는 높이보다 작거나 같으면 false를 return 해줬다.

즉 비교하고자 하는 높이(target) 보다 높은 요소만 통과(검사)할 수 있도록 해줬다.

위 조건들이 통과가 되면 방문처리로 0을 만들어주고 상, 하, 좌, 우 모두 재귀적으로 호출하여 방문처리를 해줬다.