📦 hanliang38 / Coding_Test_Practice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117## 문제설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

![](https://images.velog.io/images/kk5448599/post/e890a6c6-b4f7-45ba-8929-09f253396036/image.png)

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

![](https://images.velog.io/images/kk5448599/post/09958df1-75e1-4b46-b0a3-812762bbe38b/image.png)

- 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
- 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

![](https://images.velog.io/images/kk5448599/post/5ade932f-af7f-4d51-b31e-a7e32c18af7a/image.png)

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 `game_board`, 테이블 위에 놓인 퍼즐 조각의 상태 `table`이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

<br><br>

## 제한사항

> - 3 ≤ `game_board`의 행 길이 ≤ 50
> - `game_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`에는 반드시 하나 이상의 블록이 놓여 있습니다.

<br>

---

<br>

## 입출력 예

![](https://images.velog.io/images/kk5448599/post/38bbd8ba-455f-4fd6-94a0-3b09ea8f3902/image.png)

<br>

## 입출력 예 설명

> **입출력 예 #1**
> 입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.
> ![](https://images.velog.io/images/kk5448599/post/fa4ed30e-633a-4c05-9608-711a114525ff/image.png)

> **입출력 예 #2**
> 블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

<br>

---

<br>

~~## 풀이~~

~~## solution.js~~

## 문제 탐색 & 개념 이해

- 오늘은 문제를 풀기가 어려워서 문제의 개념과 사용되는 알고리즘에 대해 한번 정리하면서 이해하려고 한다.

> - 핵심 키워드
>   **깊이우선탐색(DFS) & 회전변환행렬(Rotation matrix)**

- 각각의 키워드에 대한 자세한 개념은 정리 후에 포스팅할 생각이다.

<br>

### 문제 탐색

먼저 제한사항을 보면 `game_board`와 `table`의 크기가 같다는 것을 알 수 있고,
`table`의 `block`은 `game_board`에 채워 넣을 때 서로 상하좌우가 인접하면 안된다.

1. 우선 `game_board`를 만들어야 하므로 `game_board`에 해당하는 배열을 만들어야 한다. (초기에는 아무것도 없으므로 0을 빈 배열의 값으로 넣는다.)
2. `table`의 퍼즐 조각을 회전한 내용까지 알아낸다.
3. `game_board`에 퍼즐이 들어가는 부분과 들어가지 않은 부분을 확인한다.

일단 문제를 보고 내가 생각한 것은 여기까지이다.

### 개념 이해

- 깊이우선탐색 (DFS)
  상하좌우의 칸들이 모두 비어있는지 채워졌는지 순차적으로 모두 확인하고 비어있고 들어갈 수 있는 퍼즐 조각을 배치한다. 그 후 같은 방식으로 다음 조각을 비교하여 배치, 저장한다.
- 회전변환행렬 (Rotation matrix)
  퍼즐조각을 회전할 수 있으므로 회전시 적용되는 행렬을 구하고 배치하기 위해 사용된다.

<br>

## 배운 점 & 느낀 점

- 예전에 코드스테이츠에서 했던 n-queens와 비슷한 느낌이 났다.
- 갑자기 난이도가 올라간듯해서 많이 당황스러웠고 문제해석과 푸는데에 걸리는 시간이 길어졌다.
- 회전변환행렬은 선형변환의 성질 중 하나라고 한다. 다양한 알고리즘을 적용하여 문제를 빠르게 풀기 위해서는 좀 더 깊게 공부할 필요가 있는 것 같다.