테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board
, 테이블 위에 놓인 퍼즐 조각의 상태 table
이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.
- 3 ≤
game_board
의 행 길이 ≤ 50game_board
의 각 열 길이 =game_board
의 행 길이
- 즉, 게임 보드는 정사각 격자 모양입니다.
game_board
의 모든 원소는 0 또는 1입니다.- 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
- 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
table
의 행 길이 =game_board
의 행 길이table
의 각 열 길이 =table
의 행 길이
- 즉, 테이블은
game_board
와 같은 크기의 정사각 격자 모양입니다.table
의 모든 원소는 0 또는 1입니다.- 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
- 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
game_board
에는 반드시 하나 이상의 빈칸이 있습니다.table
에는 반드시 하나 이상의 블록이 놓여 있습니다.
입출력 예 #1
입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.
입출력 예 #2
블록의 회전은 가능하지만, 뒤집을 수는 없습니다.
## 풀이
## solution.js
- 핵심 키워드
깊이우선탐색(DFS) & 회전변환행렬(Rotation matrix)
먼저 제한사항을 보면 game_board
와 table
의 크기가 같다는 것을 알 수 있고,
table
의 block
은 game_board
에 채워 넣을 때 서로 상하좌우가 인접하면 안된다.
game_board
를 만들어야 하므로 game_board
에 해당하는 배열을 만들어야 한다. (초기에는 아무것도 없으므로 0을 빈 배열의 값으로 넣는다.)table
의 퍼즐 조각을 회전한 내용까지 알아낸다.game_board
에 퍼즐이 들어가는 부분과 들어가지 않은 부분을 확인한다.일단 문제를 보고 내가 생각한 것은 여기까지이다.