백준2583 - 영역 구하기 (DFS) node.js

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

 

해당 문제는 DFS 알고리즘에 대해 이해하고 있다면 풀이가 쉽다.

 

문제 풀이 방식은 다음과 같다.

주어진 N,M의 값으로 기본값을 0으로하는 이차원 배열을 선언하고  

주어진 직사각형의 좌표를 통해 해당 좌표 내에 포함된 영역을 1로 수정한다.

즉 0은 이동할 수 있는 공간, 1은 이동할 수 없는 공간으로 표현되고 있는 셈이다.

 

이후 추가적으로 방문 기록을 담기 위한 이차원 배열을 선언한다.

 

DFS 알고리즘 로직을 깊이에 대한 값을 리턴할 수 있게 구현한 뒤에, 결괏값을 구할 수 있다.

 

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

function solution(data) {
  const arr = data.map((el) => el.split(" ").map(Number));
  const [N, M, _] = arr.shift();
  // 이동할 수 있는 좌표, 이동할 수 없는 좌표에 대한 데이터를 담을 2차원 배열
  const matrix = Array.from({ length: N }, () => {
    return Array.from({ length: M }, () => 0);
  });
  // 좌표별 방문 여부를 기록할 수 있는 2차원 배열
  const visited = Array.from({ length: N }, () => {
    return Array.from({ length: M }, () => false);
  });

  // 이차원 배열에 이동할 수 없는 공간 적용
  arr.forEach((el) => {
    const [x1, y1, x2, y2] = el;
    for (let i = y1; i < y2; i++) {
      for (let j = x1; j < x2; j++) matrix[i][j] = 1;
    }
  });
  
  // 이동할 수 있는 공간의 크기를 담을 배열
  const result = [];
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[0].length; j++) {
      if (!matrix[i][j] && !visited[i][j])
        result.push(DFS(matrix, visited, j, i));
    }
  }
  # 오름차순 정렬
  result.sort((a, b) => a - b);
  console.log(result.length);
  console.log(...result);
}

function DFS(matrix, visited, x, y) {
  const stack = [[x, y]];
  visited[y][x] = true;
  // 들어온 좌표가 있다면 깊이의 기본값은 1
  let dep = 1;
  while (stack.length) {
    const [x, y] = stack.pop();

    const directions = [
      [0, 1],
      [0, -1],
      [1, 0],
      [-1, 0],
    ];
    for (let i = 0; i < directions.length; i++) {
      const [dx, dy] = directions[i];
      const [nx, ny] = [dx + x, dy + y];

      if (
        verify(matrix[0].length, matrix.length, nx, ny) &&
        !visited[ny][nx] &&
        !matrix[ny][nx]
      ) {
        visited[ny][nx] = true;
        stack.push([nx, ny]);
        dep++;
      }
    }
  }
  return dep;
}

// 유효한 좌표인지 확인하기 위한 함수
function verify(X, Y, x, y) {
  return 0 <= x && x < X && 0 <= y && y < Y;
}

solution(input);