[백준] 1926번: 그림 - Node.js (자바스크립트)

1. 문제 ㅡ 1926번: 그림(난이도: Silver I)

1926번: 그림

 

2. 풀이 ㅡ Node.js (자바스크립트)

const [info, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [Y, X] = info.split(' ').map(val => +val);
const board = input.map(row => [...row.split(' ').map(val => +val)]);
const checked = Array.from({ length: Y }, () => Array.from({ length: X }, () => false));

const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0],];
const drawings = [];

const measureDrawingSize = (x, y) => {
  let size = 1;
  const queue = [[x, y]];

  while (queue.length) {
    const [x, y] = queue.shift();

    dirs.forEach(dir => {
      const xPos = dir[0] + x;
      const yPos = dir[1] + y;

      if (xPos >= 0 && yPos >= 0 && xPos < X && yPos < Y && board[yPos][xPos] && !checked[yPos][xPos]) {
        checked[yPos][xPos] = true;
        size += 1;
        queue.push([xPos, yPos]);
      }
    });
  }
  return size;
};

for (let y = 0; y < Y; y++) {
  for (let x = 0; x < X; x++) {
    if (!board[y][x] || checked[y][x]) continue;

    checked[y][x] = true;
    drawings.push(measureDrawingSize(x, y));
  }
}

console.log(drawings.length ?? 0);
console.log(drawings.length ? Math.max(...drawings) : 0);

 

2-1. 풀이 설명

입력 값을 순회하면서 값이 1인 경우, 즉 그림의 일부분인 경우 BFS 탐색을 통해 좌우상하로 연결된 모든 1의 개수를 세는 것이 문제의 핵심이다. 
 
각 그림의 사이즈 정보는 배열에 저장해두었고, 마지막에 해당 배열의 길이(총 그림 개수)와 배열에서 가장 큰 수(가장 큰 그림의 사이즈)를 출력했다.   
 

2-2. 회고

• 문제에 분명 그림이 없는 경우에는 0을 출력하라고 기재되어 있는데, 그림이 없는 경우를 따로 처리하지 않아 한 50% 정도에서 계속 오답처리 됐다.
• BFS와 점점 친해져가는 건 너무 좋지만 우선 문제부터 잘 읽자.