[프로그래머스] 지게차와 크레인

😎풀이

1. storage는 1차원 배열이므로 문자열을 나누어 2차원 배열로 정의한다.
2. request를 순회하며 2글자의 처리와 1글자일 경우의 처리를 진행한다.
   2-1. 2글자의 경우 해당 셀을 빈(null)값으로 처리한다.
   2-2. 1글자의 경우 외부와 연결되어있거나 모서리에 위치한 값인지 확인하여 접근 가능하다면 빈(null)값으로 처리한다.
3. storage를 순회하며 빈 값이 아닌 컨테이너의 수를 확인한다.
4. 확인된 컨테이너의 수를 반환한다.

function solution(storage, requests) {
  // 행(n), 열(m)
  const n = storage.length;
  const m = storage[0].length;
  
  const grid = storage.map(row => row.split(''));
  
  for (const req of requests) {
    // 요청 문자열의 첫 글자를 컨테이너 종류로 지정 (길이 2인 경우 같은 글자가 반복)
    const target = req[0];
    
    // 요청 문자열 길이가 2이면 크레인을 사용하여 해당 종류의 컨테이너를 모두 제거
    if (req.length === 2) {
      for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
          if (grid[i][j] === target) {
            grid[i][j] = null;
          }
        }
      }
    } else {
      // external: 각 빈 공간(cell이 null)에서 창고 외부와 연결되었는지 여부를 기록하는 2차원 배열
      const external = Array.from({ length: n }, () => Array(m).fill(false));
      const queue = [];
      
      // 창고의 경계(첫 행, 마지막 행, 첫 열, 마지막 열)에 있는 빈 공간은 바로 외부와 연결됨
      for (let i = 0; i < n; i++) {
        if (grid[i][0] === null && !external[i][0]) {
          external[i][0] = true;
          queue.push([i, 0]);
        }
        if (grid[i][m - 1] === null && !external[i][m - 1]) {
          external[i][m - 1] = true;
          queue.push([i, m - 1]);
        }
      }
      for (let j = 0; j < m; j++) {
        if (grid[0][j] === null && !external[0][j]) {
          external[0][j] = true;
          queue.push([0, j]);
        }
        if (grid[n - 1][j] === null && !external[n - 1][j]) {
          external[n - 1][j] = true;
          queue.push([n - 1, j]);
        }
      }
      
      // BFS를 이용하여 경계에서부터 인접한 빈 공간들을 찾아 외부와 연결된 빈 공간임을 표시
      const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
      while (queue.length > 0) {
        const [ci, cj] = queue.shift();
        for (const [di, dj] of dirs) {
          const ni = ci + di, nj = cj + dj;
          if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
          // 인접 셀이 빈 공간이고 아직 외부와 연결되지 않은 경우 표시 후 queue에 추가
          if (grid[ni][nj] === null && !external[ni][nj]) {
            external[ni][nj] = true;
            queue.push([ni, nj]);
          }
        }
      }
      
      // forklift(지게차) 요청에서는 동시에 여러 컨테이너가 제거되므로,
      // 먼저 제거할 컨테이너의 위치를 모두 수집한 후 한 번에 제거한다.
      const toRemove = [];
      for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
          // 현재 셀에 요청한 종류의 컨테이너가 있는 경우
          if (grid[i][j] === target) {
            let isAccessible = false;
            // 1. 해당 셀이 창고 경계에 있다면 바로 접근 가능
            if (i === 0 || i === n - 1 || j === 0 || j === m - 1) {
              isAccessible = true;
            } else {
              // 2. 경계가 아니라면 상하좌우 중 하나라도 빈 공간이며, 그 빈 공간이 외부와 연결되어 있어야 함
              for (const [di, dj] of dirs) {
                const ni = i + di, nj = j + dj;
                if (grid[ni][nj] === null && external[ni][nj]) {
                  isAccessible = true;
                  break;
                }
              }
            }
            // 접근 가능하면 제거할 대상으로 추가
            if (isAccessible) {
              toRemove.push([i, j]);
            }
          }
        }
      }
      
      // 수집한 위치의 컨테이너들을 제거 (빈 공간으로 만듦)
      for (const [i, j] of toRemove) {
        grid[i][j] = null;
      }
    }
  }
  
  // 모든 요청을 처리한 후, grid에서 null이 아닌(즉, 남아있는) 컨테이너의 수를 센다.
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (grid[i][j] !== null) count++;
    }
  }
  
  return count;
}