[백준 node.js] 2468번_안전 영역

백준 DFS 알고리즘 2469번_안전 영역

난이도 : 실버I

 

문제 설명

입출력

 

문제 풀이 : 문제 설명을 보면 비의 높이가 주어질때 비의 높이보다 낮은 칸들은 빗금으로 그려져있고. 그 후 영역의 요소를 카운트하면 비의 높이에 따른 안전 영역의 요소가 구해진다. 하지만 비의 높이보다 낮은 칸들을 방문처리하고 그 후 다른 영역의 요소를 구하면 두번의 그래프 탐색을 해야해서 로직이 복잡해진다. 

 

반대로 생각하여 비의 높이가 주어질때 비의 높이를 초과(문제 예시에서 4이하니깐 반대는 4초과)하는 영역을 방문처리하고 DFS의 실행횟수를 카운트하면 똑같이 안전영역의 요소를 구할 수 있다.

 

비의 높이는 1이상 100이하의 정수이므로 0~101의 반복문을 돌면서 DFS를 실행하면된다. 단 한번의 DFS를 실행하고 나면 기존의 그래프 값으로 초기화 해줘야한다. 또한 재귀이용시 범위를 초과하므로 반복문 형태로 작성한다.

 

const solution = (tmp_graph) => {
  let cnt = 0;
  let cntList = [];
  //비의 높이만큼
  for (let k = 1; k < 101; k++) {
    //그래프 모든 영역
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        //비의 높이보다 클때만 수행
        if (graph[i][j] > k) {
          DFS(i, j, k);
          //한번의 DFS수행이 끝나면 한 영역의 탐색 종료
          cnt += 1;
        }
      }
    }
    cntList.push(cnt);
    cnt = 0;
    //참조없는 복사
    //하나의 비의높이(k)를 수행한후 그래프는 기존의 값으로 초기화
    graph = JSON.parse(JSON.stringify(tmp_graph));
  }
  //배열중 최댓값 출력
  console.log(Math.max.apply(null, cntList));
};

const DFS = (i, j, k) => {
  let stack = [];
  stack.push(i);
  stack.push(j);

  while (stack.length !== 0) {
    //스택 특성상 반대로 빼줌
    let y = stack.pop();
    let x = stack.pop();
    for (let c = 0; c < dx.length; c++) {
      let nx = x + dx[c];
      let ny = y + dy[c];

      //그래프 범위안이고 비의높이(k)보다 값이 크면 방문처리
      if (RangeCheck(nx, ny) && graph[nx][ny] > k) {
        graph[nx][ny] = -1;
        stack.push(nx);
        stack.push(ny);
      }
    }
  }
};

//배열 범위 체크
const RangeCheck = (i, j) => {
  if (i >= 0 && i < n && j >= 0 && j < n) {
    return true;
  } else return false;
};

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
let n = 0;
let graph = [];
let dx = [1, -1, 0, 0];
let dy = [0, 0, 1, -1];

rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  n = Number(input.shift());
  // console.log(n);
  graph = Array.from(Array(n), () => Array(n).fill(0));

  for (let i = 0; i < n; i++) {
    graph[i] = input[i].split(" ").map((el) => Number(el));
  }

  //graph변수가 전역 변수로 설정되어 있기 때문에 깊은 복사로 통해 주소값을 제외한 데이터만 복사
  //참조없는 복사
  let tmp_graph = JSON.parse(JSON.stringify(graph));
  solution(tmp_graph);
  process.exit();
});

 

재귀방식

const DFS = (i, j, k) => {
  if (RangeCheck(i, j) && graph[i][j] > k) {
    graph[i][j] = -1;
    for (let c = 0; c < dx.length; c++) {
      DFS(i + dx[c], j + dy[c], k);
    }
  }
};

 

 

* 맨처음에  let tmp_graph = graph; 로 값을 넣어주고 이용했다. 제대로된 출력값이 안나오길래 디버깅을 통해 확인해보니깐 graph를 전역변수로 사용하고 있기 때문에 graph값이 바뀌는 순간 tmp_graph도 바뀌는것을 확인할 수 있었다.

미처 참조복사와 값복사(얕은 복사와 깊은 복사)를 신경쓰지 못했다.

또한 2583영역 구하기 문제도 그렇고 재귀깊이가 100을 초과하면 런타임에러가 난다.

웬만해선 그냥 반복문으로 푸는 방식을 익히는게 속편한 것 같다.