백준21938 - 영상처리 (BFS) node.js

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

 

문제 풀이 방식

먼저 픽셀 값에 따른 물체의 유무를 저장하기 위한 이차원 배열을 만들었다. 

이후 반복문으로 순회하며 rgb값의 평균값을 구하고 해당 값이 경계값을 넘는다면, 이차원 배열의 해당 위치를 'true'로 설정하여 물체가 있음을 저장하였다.

다음으로는 너비우선탐색 알고리즘을 활용하여, 분리된 '물체'가 총 몇개인지 누산하는 방식으로 문제를 해결하였다.

 

전체 소스 코드

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

function solution(data) {
  const [[N, M], ...arr] = data.map((el) => el.split(" ").map(Number));
  const [T] = arr.pop();

  const matrix = Array.from({ length: N }, () => {
    return Array.from({ length: M }, () => false);
  });

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M * 3; j += 3) {
      const avg = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2]) / 3;

      if (avg >= T) matrix[i][Math.floor(j / 3)] = true;
    }
  }

  const visited = Array.from({ length: N }, () => {
    return Array.from({ length: M }, () => false);
  });

  function locationVerify(x, y) {
    return 0 <= x && x < M && 0 <= y && y < N;
  }

  function BFS(x, y) {
    const queue = [[x, y]];
    let queueIdx = 0;
    const directions = [
      [0, 1],
      [1, 0],
      [-1, 0],
      [0, -1],
    ];

    while (queueIdx < queue.length) {
      const [x, y] = queue[queueIdx++];

      if (visited[y][x]) continue;
      visited[y][x] = true;

      directions.forEach(([dx, dy]) => {
        const [nx, ny] = [dx + x, dy + y];
        if (locationVerify(nx, ny) && matrix[ny][nx] && !visited[ny][nx]) {
          queue.push([nx, ny]);
        }
      });
    }
  }

  let result = 0;

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (matrix[i][j] && !visited[i][j]) {
        BFS(j, i);
        result++;
      }
    }
  }

  console.log(result);
}

solution(input);