[Javascript] 프로그래머스 - 퍼즐 조각 채우기

문제 설명

정사각형 형태의 게임 보드와 테이블이 주어집니다. 게임 보드의 빈 공간(0)과 테이블 위의 퍼즐 조각(1)을 활용해 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워야 합니다. 조각은 회전할 수 있지만 뒤집을 수는 없으며, 인접한 칸에 빈 공간이 생기지 않도록 배치해야 합니다.

---

제한 사항

• 게임 보드와 테이블의 크기: 3 ≤ N ≤ 50 (N × N 정사각형 격자)
• 0: 빈 칸, 1: 조각이 놓인 칸
• 퍼즐 조각 크기: 최소 1 × 1 ~ 최대 6 × 6 연결된 형태
• 게임 보드와 테이블은 반드시 하나 이상의 빈 칸 또는 조각을 포함

---

해결 방법

알고리즘: BFS, 회전, 맵(HashMap)

1. 퍼즐 조각 탐색:
   • BFS를 사용해 테이블과 게임 보드의 퍼즐 조각을 탐색합니다.
   • 각 조각의 모양을 추출하고, 크기와 경계 정보를 계산하여 조각의 고유한 형태를 생성합니다.
2. 퍼즐 조각 회전:
   • 각 조각을 4가지 회전 방향으로 변환하여 모든 가능한 경우를 탐색합니다.
3. 퍼즐 조각 매칭:
   • 테이블에서 추출한 퍼즐 조각의 회전된 형태를 게임 보드의 빈 공간과 비교합니다.
   • 매칭된 조각은 게임 보드에 채워지며, 조각의 크기만큼 결과값에 추가됩니다.
4. 맵(HashMap)을 이용한 중복 처리:
   • 조각 형태를 문자열로 변환하여 HashMap에 저장하고, 동일한 조각이 여러 번 사용되지 않도록 관리합니다.

---

시간 복잡도

• BFS 탐색: O(N^2) (보드 전체를 탐색)
• 조각 회전 및 비교: O(N^2 * R) (각 조각에 대해 4번의 회전)
• 전체 시간 복잡도: O(N^2 * M), M은 보드 및 테이블에 있는 조각의 개수

---

구현 코드

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  push(value) {
    const node = new Node(value);

    if (this.size === 0) {
      this.rear = node;
      this.front = node;
    } else {
      this.rear.next = node;
      this.rear = node;
    }

    ++this.size;
  }

  pop() {
    if (this.size === 0) {
      return null;
    }

    const value = this.front.value;

    --this.size;

    this.front = this.front.next;
    if (this.size === 0) {
      this.rear = null;
    }

    return value;
  }
}

function rotate(board, d) {
  let map = [];
  let yLen = board.length - 1;
  let xLen = board[0].length - 1;

  if (d === 0) {
    for (let i = 0; i <= yLen; ++i) {
      let temp = [];
      for (let j = 0; j <= xLen; ++j) {
        temp.push(board[i][j]);
      }
      map.push(temp);
    }
  } else if (d === 1) {
    for (let i = xLen; i >= 0; --i) {
      let temp = [];
      for (let j = 0; j <= yLen; ++j) {
        temp.push(board[j][i]);
      }
      map.push(temp);
    }
  } else if (d === 2) {
    for (let i = yLen; i >= 0; --i) {
      let temp = [];
      for (let j = xLen; j >= 0; --j) {
        temp.push(board[i][j]);
      }
      map.push(temp);
    }
  } else if (d === 3) {
    for (let i = 0; i <= xLen; ++i) {
      let temp = [];
      for (let j = yLen; j >= 0; --j) {
        temp.push(board[j][i]);
      }
      map.push(temp);
    }
  }

  return map;
}

function filterMap(board, x1, x2, y1, y2, num) {
  return board
    .slice(y1, y2 + 1)
    .map((row) => row.slice(x1, x2 + 1).map((item) => (item === num ? 1 : 0)));
}

function isValidRange(y, x, size) {
  return y >= 0 && x >= 0 && y < size && x < size;
}

function countSize(str) {
  return str.split("").filter((char) => char === "1").length;
}

function getShape(q, index, boardSize, board) {
  const moveY = [0, 1, 0, -1];
  const moveX = [1, 0, -1, 0];
  let xMin = boardSize;
  let xMax = 0;
  let yMin = boardSize;
  let yMax = 0;

  while (q.size > 0) {
    const [y, x] = q.pop();

    board[y][x] = index;
    yMin = Math.min(yMin, y);
    yMax = Math.max(yMax, y);
    xMin = Math.min(xMin, x);
    xMax = Math.max(xMax, x);

    for (let i = 0; i < 4; ++i) {
      const nextY = y + moveY[i];
      const nextX = x + moveX[i];

      if (isValidRange(nextY, nextX, boardSize) && board[nextY][nextX] === 0) {
        q.push([nextY, nextX]);
        board[nextY][nextX] = index;
      }
    }
  }

  return filterMap(board, xMin, xMax, yMin, yMax, index);
}

function solution(game_board, table) {
  let answer = 0;
  const q = new Queue();
  const map = new Map();
  const boardSize = game_board.length;
  let index = 2;
  table = table.map((row) => row.map((item) => (item ? 0 : 1)));

  for (let i = 0; i < boardSize; ++i) {
    for (let j = 0; j < boardSize; ++j) {
      if (game_board[i][j] === 0) {
        q.push([i, j]);
        const shape = getShape(q, index, boardSize, game_board);
        const key = JSON.stringify(shape);
        map.set(key, map.has(key) ? map.get(key) + 1 : 1);
        ++index;
      }
    }
  }

  for (let i = 0; i < boardSize; ++i) {
    for (let j = 0; j < boardSize; ++j) {
      if (table[i][j] === 0) {
        q.push([i, j]);
        const shape = getShape(q, index, boardSize, table);

        for (let k = 0; k < 4; ++k) {
          const rotatedShape = rotate(shape, k);
          const key = JSON.stringify(rotatedShape);

          if (map.has(key)) {
            answer += countSize(key);
            if (map.get(key) === 1) {
              map.delete(key);
            } else {
              map.set(key, map.get(key) - 1);
            }
            break;
          }

          ++index;
        }
      }
    }
  }

  return answer;
}