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

문제 설명

물류창고에는 알파벳 대문자로 구분되는 컨테이너들이 n×m 크기의 격자로 배치되어 있다. 출고 요청이 들어올 때, 요청된 컨테이너를 창고에서 꺼내야 한다.

• 지게차를 사용하면 창고 외부와 연결된 동일 종류의 컨테이너만 출고된다.
• 크레인을 사용하면 해당 종류의 모든 컨테이너를 출고할 수 있다.

모든 요청을 수행한 후 남아있는 컨테이너의 개수를 구하는 문제이다.

---

제한 사항

• 2 ≤ n, m ≤ 50
• storage는 알파벳 대문자로 구성된 2차원 배열
• requests의 길이는 1 이상 100 이하
• requests[i]는 한 종류의 알파벳 대문자로 이루어진 문자열(길이 1이면 지게차, 길이 2이면 크레인)

---

해결 방법

알고리즘: BFS, 구현

1. 창고 확장 및 경계 설정
   • n+2 × m+2 크기의 새로운 배열을 생성하여 외부 경계를 -1로 설정한다.
   • 기존 데이터를 중앙에 배치해 경계를 손쉽게 판단할 수 있도록 한다.
2. 창고 외부 영역 식별 (BFS 탐색)
   • 외부 공기와 연결된 빈 공간을 BFS로 탐색하면서 -1로 표시한다.
   • 지게차 출고 시, 외부와 연결된 컨테이너 판별을 쉽게 하기 위함이다.
3. 출고 요청 처리
   • 요청이 길이 1이면 지게차를 사용해 외부와 인접한 컨테이너만 제거한다.
   • 요청이 길이 2이면 크레인을 사용해 해당 종류의 컨테이너를 모두 제거한다.
   • 출고 이후 다시 BFS를 수행하여 외부와 연결된 공간을 갱신한다.
4. 남은 컨테이너 개수 계산
   • BFS 완료 후 남아있는 컨테이너 개수를 세어 반환한다.

---

시간 복잡도

• updateExternal(): BFS 탐색 O(nm)
• 각 요청 처리 시 O(nm)
• 최대 요청 개수 100개이므로 최악의 경우 O(100 × nm) = O(5000 × 50) ≈ 250,000

---

구현 코드

function solution(storage, requests) {
  const n = storage.length,
    m = storage[0].length;
  const grid = Array.from({ length: n + 2 }, (_, i) =>
    Array.from({ length: m + 2 }, (_, j) =>
      i === 0 || j === 0 || i === n + 1 || j === m + 1 ? -1 : storage[i - 1][j - 1]
    )
  );

  const moves = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];

  function updateExternal() {
    const rows = grid.length,
      cols = grid[0].length;
    const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
    const queue = [[0, 0]];
    visited[0][0] = true;

    while (queue.length) {
      const [y, x] = queue.shift();
      for (const [dy, dx] of moves) {
        const ny = y + dy,
          nx = x + dx;
        if (ny < 0 || nx < 0 || ny >= rows || nx >= cols || visited[ny][nx]) continue;
        if (typeof grid[ny][nx] === "number") {
          grid[ny][nx] = -1;
          visited[ny][nx] = true;
          queue.push([ny, nx]);
        }
      }
    }
  }

  for (let idx = 0; idx < requests.length; idx++) {
    const req = requests[idx];
    const target = req[0];
    if (req.length === 1) {
      for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
          if (grid[i][j] !== target) continue;
          for (const [dy, dx] of moves) {
            if (grid[i + dy][j + dx] === -1) {
              grid[i][j] = idx;
              break;
            }
          }
        }
      }
    } else {
      for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
          if (grid[i][j] === target) grid[i][j] = Infinity;
        }
      }
    }
    updateExternal();
  }

  let answer = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (typeof grid[i][j] === "string") answer++;
    }
  }

  return answer;
}