[JS] 지게차와 크

문제

프로그래머스

 

풀이

이 문제의 키 포인트는 두가지로 생각한다.

 

첫 번째, 외각에 있는 요소 체크 후 제거. 이는 테두리에 있는 요소를 확인하는 것은 이 요소가 지게차로 제거할 수 있는지 확인하는 것이다. 나는 -1이라는 값을 이용해 BFS 알고리즘으로 4 방향으로 확인하며 탐색을 진행했다.

 

두 번째, 제거된 블럭으로 인해 태두리에 위치하게 되는 요소의 계산이다. 예를 들어보자.

위의 사진과 같이 물건들이 있다고 가정하자. 명령어는 ["BB", "A"]가 주어졌을때, "BB" 명령어가 먼저 시행되며 해당 물건들에서 B 요소들은 모두 테두리와 상관없이 모두 제거된다. 제거된 요소는 0으로 표시한다.

 

이제 다음 명령을 시행하면 다음과 같아진다. 외각에서 제거된 요소는 -1로 표시한다.

자 이제 -1과 0이 만나는 경우가 생겼다. 그렇다면 2행에 있는 C는 태두리가 된다. 이때 필드의 값을 계산하며 태두리에 있는 요소인지 확인하면된다.

 

 

코드

function solution(storage, requests) {
  const [n, m] = [storage.length, storage[0].length];
  let answer = 0;
  let double = new Set();
  let map = Array.from({ length: n + 2 }, () => Array.from({ length: m + 2 }, () => -1));
  const dir = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1]
  ];
    
  for (let i = 0; i < storage.length; i++) {
    for (let j = 0; j < storage[i].length; j++) {
      map[i + 1][j + 1] = storage[i][j];
    }
  }
    
  for (let req of requests) {
    // 지게차 작업
    if (req.length === 1) {
      if (double.has(req)) continue;
      let visited = new Set();
      let que = [[0, 0]];
      visited.add('0, 0', true);
            
      while (que.length > 0) {
        const [x, y] = que.shift();
        for (let [dx, dy] of dir) {
          const [nx, ny] = [x + dx, y + dy];
          if (nx >= 0 && nx < n + 2 && ny >= 0 && ny < m + 2 && !visited.has(`${nx}, ${ny}`)) {
            if (map[nx][ny] === -1) que.push([nx, ny]);
            else if (map[nx][ny] === req) map[nx][ny] = -1;
            else if (map[nx][ny] === 0) {
              que.push([nx, ny]);
              map[nx][ny] = -1;
            }
            visited.add(`${nx}, ${ny}`, true);
          }
        }
      }
    }
        
    // 크레인 작업
    else {
      double.add(req[0], true);
      for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
          if (map[i][j] === req[0]) {
            if (dir.some(([x, y]) => map[i + x][j + y] === -1)) {
              map[i][j] = -1;
            } else map[i][j] = 0;
          }
        }
      }
    }
  }
  for (let i = 1; i < n + 1; i++) {
    for (let j = 1; j < m + 1; j++) {
      if (map[i][j] !== 0 && map[i][j] !== -1) answer++;
    }
  }
  return answer;
}