[백준] 2468번 : 안전 영역 (실버Ⅰ) by node.js

▷ 문제 : 2468번 - 안전 영역

2468번: 안전 영역

▷ 해결 날짜 : 2022.07.14
▷ 소요 시간 : 1시간
▷ 풀이 과정 :

문제를 요약하자면 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력하는 문제이다.

여기서 장마철의 강수량은 알 수 없고, 그저 강수량에 따라서 물에 잠기지 않는 안전한 영역의 개수가 다르게 되는데, 그중에서 최대 값을 출력해야 한다.

 

우선 각 지점의 높이가 주어지니 거기서 최댓값을 따로 저장해 두고, 강수량을 1부터 최댓값까지 계속해서 높여가며 처음부터 모든 배열의 위치를 스캔해가는 방향으로 풀어보았다.

 

결국 인접한(상하좌우) 모든 영역을 안전한 영역 1로 보고 개수를 구하는 것이기 때문에, 스캔의 시작점부터 시작해서 인접하는 곳을 모조리 방문하고 방문이 끝나면 다시 다음 시작점을 찾아가면 되는 문제이다.

 

그렇게 개수를 구한 다음 현재 최댓값과 계속 비교해가며 값을 구하면 된다.

 

▷ 구현

let fs = require("fs");
let input = fs.readFileSync("./dev/stdin").toString().split("\n");

const ds = [
  [-1, 0],
  [1, 0],
  [0, 1],
  [0, -1],
];
const N = Number(input.shift());
const areas = [];
let visited = [];

let [min, max] = [1, 1];
for (let i = 0; i < N; i++) {
  const area = input[i].split(" ").map(Number);
  const newMax = Math.max(...area);
  if (newMax > max) max = newMax;

  areas.push(area);
}

const bfs = (startX, startY) => {
  const queue = [[startX, startY]];
  while (queue.length) {
    const [x, y] = queue.shift();
    if (areas[x][y] > min && visited[x][y]) continue;
    else visited[x][y] = 1;

    for (let i = 0; i < 4; i++) {
      const xPos = x + ds[i][0];
      const yPos = y + ds[i][1];

      if (xPos < 0 || yPos < 0 || xPos >= N || yPos >= N) continue;
      if (areas[xPos][yPos] > min && !visited[xPos][yPos])
        queue.push([xPos, yPos]);
    }
  }
};
let answer = 1;
while (min < max) {
  visited = [...Array(N)].map((v) => Array(N).fill(0));
  let count = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (areas[i][j] > min && !visited[i][j]) {
        bfs(i, j);
        count++;
      }
    }
  }
  if (count > answer) answer = count;
  min++;
}

console.log(answer);

 

▷ 복기 :

사실 다 풀고 나서 시간 초과에 걸리면 어쩌지 싶었는데, 다행히 시간 초과는 걸리지 않고 while 조건을 잘못 걸어서 시간을 좀 소비하였다.

그래도 어떻게 풀긴 풀었는데, 맞나 싶기도 하고 더 좋은 방법이 없을까 생각하게 된다.