[백준/JS] 2468 안전영역

문제링크

문제풀이

bfs 혹은 dfs를 사용해서 풀면 되는 문제입니다!!

조건에서 따로 비의 양이 주어지지 않기 때문에 모든 경우의 비의 양을 고려해야 합니다.

다만 지도에 나와있는 높이 중 최대 높이일 경우까지만 비교해주면 됩니다.

(최소 높이 부터 최대 높이라고 생각했지만 최소 높이부터 구할경우 정답이 아니게 됩니다. 이유는 비가 오지 않는 즉, 0인 경우가 최대의 영역이 되는 경우도 있기 때문입니다.) -> 이거 때문에 첨에 틀렸습니두앗....

따라서 비의 양에 따른 경우의 수만큼 탐색을 진행해주면 됩니다.

수도코드로 나타내면 아래와 같습니다!

for(비의 양 경우의 수 (0 부터 최대 높이까지)){

	영역개수=0
/* visited를 모두 초기화 해야한다 !!중요!!
   이유는 우리는 비의 양이 달라질 때 마다
   모든 좌표에 대해서 탐색을 다시 진행해야 하므로
   visitied를 초기화 해주어야 합니다. */
	visited=false 

	이중 for(모든 좌표){
		bfs()
		영역갯수++;
	}

	if 영역갯수 > 최대 영역갯수 
			영역갯수 갱신하기

}

결과 코드

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

let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];
let h_max = 0;
let ans_max = 0;

let N = Number(input.shift());
let visited = Array.from(Array(N), () => Array(N).fill(false));

let map = [];
for (let i = 0; i < N; i++) {
  let arr = input.shift().split(" ").map(Number);
  map.push(arr);

  h_max = Math.max(h_max, Math.max(...arr));
}

function bfs(sx, sy, height) {
  let queue = [[sx, sy]];

  while (queue.length) {
    let [x, y] = queue.shift();
    visited[x][y] = true;

    for (let d = 0; d < 4; d++) {
      let nx = x + dx[d];
      let ny = y + dy[d];

      if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

      if (!visited[nx][ny] && map[nx][ny] > height) {
        visited[nx][ny] = true;
        queue.push([nx, ny]);
      }
    }
  }
}

for (let i = 0; i < h_max; i++) {
  let cnt = 0;
  for (let c = 0; c < N; c++) {
    for (let d = 0; d < N; d++) {
      visited[c][d] = false;
    }
  }

  for (let a = 0; a < N; a++) {
    for (let b = 0; b < N; b++) {
      if (map[a][b] > i && !visited[a][b]) {
        bfs(a, b, i);
        cnt++; //영역갯수
      }
    }
  }

  ans_max = Math.max(ans_max, cnt);
}

console.log(ans_max);

.
.
.
.
.
.
.

잡담

bfs, dfs 문제모음을 풀어서 그럴지는 몰라도 확실히 프로그래머스보다는 복잡한 구현같은 것들이 적어서 먼가... 좋긴하지만 그래도 자꾸 실수하는 제가 넘 화나는거 있쪄ㅣ..^^ 크킄ㅋ 우리 모두 힘내요 아좌뵤