백준1926 - 그림 (DFS) node.js

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

해당 문제에서는 '그림'의 크기와 그림에 대한 데이터가 주어진다. 이때 '1'이 색칠된 부분이라고 할 때, 색칠된 그림의 갯수와 가장 넓은 크기를 출력하는 문제다.

 

문제 풀이 방식

연결된 그림의 크기를 구해야 하기 때문에 DFS 알고리즘을 활용하여 접근하되, 그림에 대한 번호와, 각 번호에 따른 크기를 추가하는 로직만 추가하면 풀이가 쉬운 편이었다. (그림이 하나도 없는 경우에는 0을 출력하는 것만 주의하면 된다.)

 

전체 소스 코드

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();

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

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

  function DFS(x, y, tag) {
    const stack = [[x, y]];
    visited[y][x] = tag;
    const directions = [
      [0, 1],
      [0, -1],
      [1, 0],
      [-1, 0],
    ];
    while (stack.length) {
      const [x, y] = stack.pop();

      directions.forEach(([dx, dy]) => {
        const [nx, ny] = [dx + x, dy + y];
        if (verify(nx, ny) && !visited[ny][nx] && arr[ny][nx] == 1) {
          visited[ny][nx] = tag;
          stack.push([nx, ny]);
          paints[tag] += 1;
        }
      });
    }
  }
  let tags = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (arr[i][j] === 1 && !visited[i][j]) {
        tags++;
        paints[tags] = 1;
        DFS(j, i, tags);
      }
    }
  }

  const max = Object.values(paints).length
    ? Math.max(...Object.values(paints))
    : 0;
  console.log(tags);
  console.log(max);
}

solution(input);