[algorithm] 백준 1926 - 그림, BFS

[문제] 백준 알고리즘 1926, 그림
[링크] https://www.acmicpc.net/problem/1926
푸는데 걸린 시간: 약 5시간

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

const picture = [];
for (let i = 0; i < n; i++) {
  picture[i] = input[i + 1].split(' ');
}

const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];

const bfs = picture => {
  let count = 0;
  let biggestArea = 0;
  const queue = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (picture[i][j] === '1') {
        count++;
        queue.push([i, j]);
        picture[i][j] = '0';
        let area = 1;
        // 연결된 그림 조각 다 찾아내기
        while (queue.length) {
          let tmp = queue.shift();
          for (let i = 0; i < 4; i++) {
            let x = tmp[1] + dx[i];
            let y = tmp[0] + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n) {
              if (picture[y][x] === '1') {
                picture[y][x] = '0';
                area++;
                queue.push([y, x]);
              }
            }
          }
        }
        biggestArea = Math.max(biggestArea, area);
      }
    }
  }
  return [count, biggestArea];
}

const result = bfs(picture);
console.log(result[0]);
console.log(result[1]);

포인트

1. 한 점에서 상하좌우로 이동하는 방법으로 아래의 배열을 사용한 것
2. const dx = [1, 0, -1, 0]; const dy = [0, 1, 0, -1];
3. 왜 BFS인가
   한 점에서 상하좌우로 다 움직이면서 가능한 점(1인 점)을 연결해나가야 하기 때문이다.
   만약 DFS로 한다면 불가능할 것이다.
4. 시행착오
   처음 VScode 로 잘 됐으나, 백준에 제출하는 과정에 시간초과가 나왔다.
   [원인]
   그림 전체에서 1인 점 하나를 찾는 함수를 따로 만들어서 새로운 그림을 찾기 시작할 때마다 그림판 전체를 스캔하게 만들었던 것이다.
   최악의 경우, n x m 인 지점에 마지막 그림(크기가 1인)이 있는 경우 불필요하게 첫 점부터 마지막까지 다 스캔하게 된다.
   마지막 점이라서 이미 다른 점들에는 visited 표시(코드에서는 '0')가 붙었음에도 말이다.
   [해결]
   애초 첫점부터 마지막 점까지 2중 반복문으로 순환하면서 그 안에서 BFS 로직을 구현하는 것이다.
   이어진 점들은 실행과정에 '0'이 될 것이고, '0'인 점들은 2중 반복문 순환 과정에서 스킵될 것이다.
   [배운점]
   모듈화(?)를 본따서 특정 기능을 수행하는 함수를 따로 만드는 것이 항상 좋은 것은 아니다.
   보기는 좋을지 모르나 실행시간이나 메모리측면을 고려하면서 사용해야한다는 것을 배웠다.