[JavaScript] 프로그래머스 위클리 챌린지 3주차 퍼즐 조각 채우기

문제 링크

• 코딩테스트 연습 > 위클리 챌린지 > 퍼즐 조각 채우기

문제 접근

1. 빈 공간의 블록 모양을 파악한다. (회전 고려X)

2. 퍼즐 조각의 모양을 파악한다. (4방향 회전을 모두 고려한다.)

3. 퍼즐 조각과 일치하는 빈 블록 모양이 있는 지 확인한다.

   • 일치한다면, 이후의 퍼즐 조각은 해당 빈 블록은 비교하지 않는다.
     (해당 빈 블록은 이제 채워진 상태이다.)

   • 일치하지 않는다면, 다음 빈 블록 모양과 비교하거나 다음 빈 블록 모양이 없다면 다음 퍼즐 조각으로 넘어간다.

• 빈 공간의 블록 모양은 회전을 고려하지 않는 이유 : 퍼즐 조각을 4방향으로 돌려 빈 공간과 일치하는 지 확인할 것이기 때문

문제 풀이

getShape(arr, baseX, baseY)

arr[baseX][baseY]를 기준으로 arr[baseX][baseY]와 같은 value를 가지는 인접한 칸의 행과 열의 좌표를 구한다.

// 하나의 모양의 좌표들 구하기
const getShape = (arr, baseX, baseY) => {
  const shape = [];
  const value = arr[baseX][baseY];

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

  // value값과 같은 인접한 좌표들을 탐색
  const bfs = (x, y, value) => {
    if (arr[x][y] !== value) return;

    shape.push([x - baseX, y - baseY]);
    arr[x][y] = value ? 0 : 1;

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (
        nx >= 0 &&
        nx < arr.length &&
        ny >= 0 &&
        ny < arr.length &&
        arr[nx][ny] === value
      ) {
        bfs(nx, ny, value);
      }
    }
  };

  bfs(baseX, baseY, value);

  return shape;
};

findShapes(arr, value)

arr 에서 value 값을 가지는 모양들을 찾는다.
arr를 돌면서 모양의 시작 지점을 찾아 getShape()함수를 호출해 찾은 shape들의 배열을 리턴한다.

const findShapes = (arr, value) => {
  const shapes = [];

  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[i][j] === value) {
        shapes.push(getShape(arr, i, j));
      }
    }
  }

  return shapes;
};

getRotatedShapes(shape)

모양의 좌표값들을 오른쪽으로 90도 180도 270도로 회전했을 때 좌표값을 구한다.

const getRotatedShapes = shape => {
  const rotatedShapes = [shape];

  for (let i = 0; i < 3; i++) {
    const lastShapeIdx = rotatedShapes.length - 1;

    rotatedShapes.push(
      rotatedShapes[lastShapeIdx].map(([x, y]) => [-y || 0, x])
    );
  }

  return rotatedShapes;
};

normalizeShape(shape)

회전시킨 모양의 좌표들을 모두 (0,0)을 기준으로 좌표값을 가지도록 변환한다.
(음의 좌표값이 없도록 정규화한다.)

const normalizeShape = shape => {
  const [row, col] = shape.reduce(
    (acc, cur) => [Math.min(acc[0], cur[0]), Math.min(acc[1], cur[1])],
    [Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER]
  );

  return shape
    .map(([r, c]) => [row < 0 ? r - row : r, col < 0 ? c - col : c])
    .sort()
    .flat()
    .join('');
};

solution()

puzzleShapes

table에서 퍼즐들의 모양을 회전가능한 경우의 수를 모두 고려하여 구한다.

blankShapes

game_board에서 빈 공간의 모양을 구한다.
(이 때는 회전가능한 경우의 수까지 고려하지 않아도 된다.)

blankShapes.forEach()

game_board의 빈 공간들이 table에서 가져온 블록들의 경우의 수 중에 존재하는 지 확인 후, 존재한다면 그 블록은 다음부턴 확인하지 않고, 그 블록의 칸수만큼 answer에 더해준다.

function solution(game_board, table) {
  const PUZZLE_VALUE = 1;
  const BLANK_VALUE = 0;

  const puzzleShapes = findShapes(table, PUZZLE_VALUE)
    .map(shape => getRotatedShapes(shape))
    .map(rotatedShape => rotatedShape.map(shape => normalizeShape(shape)));

  const blankShapes = findShapes(game_board, BLANK_VALUE).map(shape =>
    normalizeShape(shape)
  );

  let answer = 0;
  blankShapes.forEach(shape => {
    for (let i = 0; i < puzzleShapes.length; i++) {
      if (puzzleShapes[i].includes(shape)) {
        puzzleShapes.splice(i, 1);
        answer += Math.floor(shape.length / 2);
        break;
      }
    }
  });

  return answer;
}