[백준 node.js] 2583번_영역 구하기

백준 DFS 알고리즘 2583번_영역 구하기

난이도 : 실버I

 

문제 설명

입출력

입출력 추가

예제 입력2 :

00 100 1
0 0 1 1

예제 출력2 :

1
9999

 

 

문제 풀이 : 이 문제는 조금 까다로워서 고려해야할 사항이 많다.

1. 문제 예시에서는 그래프의 0.0을 제일 왼쪽밑에서 부터시작한다. 수학시간에서 배운 x축 y축 좌표로 표현한다.

2. 눈금 크기가 100이하라서 재귀 DFS를 사용하면 정해진 재귀횟수를 넘어가서 런타임 에러가 발생한다.

3. 직사각형이 그려진 이외의 곳을 탐색해야한다.

 

크게 이 두가지 조건을 해결해야한다. 방법은 다음과 같다.

1. 기존의 0.0처럼(제일 왼쪽 위) 사용하기 위해선 입력으로 받은 x,y값을 바꿔주면된다. 이렇게 되면 상하 반전이 된다.

상하 반전이되면 원래의 직사각형의 위치가 달라지지만 영역의 넓이와는 무관하다.

2. 재귀DFS 대신, stack과 반복문을 통한 DFS를 구현한다.

3. 직사각형의 위치가 아닌곳은 0이기 때문에 0인 곳만 DFS탐색을 하면된다. (방문처리는 1로 처리)

 

//실버1 영역 구하기
const solution = () => {
  let cnt = [];
  //모든 그래프를 돌면서 0일때만 DFS실행
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (graph[i][j] === 0) {
        //DFS한번 수행후 한곳의 영역이 전부 방문처리됨
        cnt.push(DFS(i, j));
      }
    }
  }

  cnt.sort((a, b) => a - b);
  console.log(cnt.length); //배열 길이가 곧 영역의 개수
  console.log(cnt.join(" "));
};

//재귀로 작성시 재귀깊이로 인한 런타임 에러때문에 반복문으로 작성
const DFS = (i, j) => {
  //첫번째 단계 셋팅
  let stack = [];
  stack.push(i);
  stack.push(j);
  graph[i][j] = 1; //방문처리
  let num = 1; //영역의 넓이 변수

  //첫번째 이후 계속 반복 DFS재귀와 동일
  while (stack.length !== 0) {
    //스택특성상 꺼꾸로 y,x에 대입
    let y = stack.pop();
    let x = stack.pop();
    for (let k = 0; k < dx.length; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      //배열 범위안이거나 방문한적이 없다면
      if (RangeCheck(nx, ny) && graph[nx][ny] === 0) {
        stack.push(nx); //현재 위치 스택에 삽입
        stack.push(ny);
        graph[nx][ny] = 1; //방문처리
        num += 1; //영역의 넓이 누적 계산
      }
    }
  }
  //한 영역의 탐색이 끝나면 영역의 넓이 반환
  return num;
};

//그래프(배열) 범위 검증
const RangeCheck = (i, j) => {
  if (i >= 0 && i < m && 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 graph = [];
let [m, n, k] = [0];
//영역의 넓이
let sum = 0;
//상하좌우
let dx = [-1, 1, 0, 0];
let dy = [0, 0, -1, 1];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  [m, n, k] = input
    .shift()
    .split(" ")
    .map((el) => Number(el));

  graph = Array.from(Array(m), () => Array(n).fill(0));

  for (let i = 0; i < k; i++) {
    //제일 왼쪽 위를 0,0으로 사용하기 위해
    //상하 반전을 위해 x,y값 반대로 입력
    let [y1, x1, y2, x2] = input
      .shift()
      .split(" ")
      .map((el) => Number(el));

    //그래프에 도형 그리기
    for (let x = x1; x < x2; x++) {
      for (let y = y1; y < y2; y++) {
        graph[x][y] = 1;
      }
    }
  }
  //함수실행
  solution();
  process.exit();
});

 

재귀함수 로직

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

 

* 문제 유형자체는 일반 DFS와 같은데  문제의0.0은 제일 왼쪽 밑에서 부터 시작해서 그것을 기존 배열시작값(제일 왼쪽 위)로 바꿔주기 위해 좌표를 어떻게 계산해야할지 엄청 계산하고 고민했다. 다른 블로그를 참고한 결과 상하 반전을 통해 해결할 수 있었다. 그 후 똑같이 재귀DFS처럼 풀고 제출했는데 런타임 에러가 났다.

백준 질문사이트에서 찾아보니 재귀 깊이 때문이라고 나와있었다. 입력 범위를 보면 100까지라서 재귀범위를 초과할 수 있기 때문이다. 파이썬 같은 경우는 코드내에 설정을 통해 재귀 깊이를 정할수 있다고 나와있지만 node.js는 실행할때 조건을 줘야지 적용이된다해서 그냥 반복문을 통해 해결하기로 했다 ㅠㅠㅠ 맨날 재귀로만 해결해서 반복문으로 짜는것은 어색해서 멈칫했지만 해결했다.  

DFS작성시 재귀방법과 while방법 두가지 모두 연습하길 추천한다.