💡 생각하자
⨉ 크기의 정사각형에 1x1 한 칸을 제외하고 항상 L-Tromino로 모두 채울 수 있다.
지금부터 편의를 위해 정사각형 한 변의 길이를 n으로 둔다.
(단, n은 2의 거듭제곱)
한 변의 길이가 n인 정사각형에서 'X'가 속한 사분면을 확인하고, 해당 사분면을 제외한 나머지 3개의 사분면에 4등분 선을 중심으로 1칸씩 채워서 L-Tromino 하나를 생성한다.
다음으로, 한 변의 길이가 n/2인 정사각형 4개를 대상으로 똑같이 실시한다.
단, 여기서부터 이미 채워진 사각형은 'X'와 같은 취급을 한다.
그러므로 첫번째 정사각형에서는 '1'이 속한 4사분면을 제외한 1, 2, 3사분면의 중심에 L-Tromino를 생성한다.
💻 구현하자
- 채워진 사각형이 어느 사분면에 있는지 판단하는 함수
int DetQuadrant(Pos origin, Pos sel) {
if (sel.x < origin.x && sel.y < origin.y) return 1;
else if (sel.x < origin.x && sel.y >= origin.y) return 2;
else if (sel.x >= origin.x && sel.y < origin.y) return 3;
else return 4;
}- origin: 해당 정사각형에서 중심이 되는 점의 좌표
EX 1) 4 by 4 정사각형에서는 (1, 1)
EX 2) 8 by 8 정사각형을 4등분 했을 때, 두번째 정사각형에서는 (2, 6)
- L-Tromino를 생성하는 함수
void makeLTromino(int flag, Pos start) { // for 2 by 2 square
for (int i = 0, temp = 1;i < 2;i++) {
for (int j = 0; j < 2;j++, temp++) {
if (temp == flag)
continue; // selected quadrant is already filled or has 'X'
square[start.x + i][start.y + j] = cnt;
}
}
cnt++;
}1사분면부터 4사분면까지 차례로 돌면서, 한 변의 길이가 n인 정사각형의 중심에 L-Tromino를 생성한다. (이미 칠해진 사분면(flag)을 제외하고)
void fill(int n, Pos ori, Pos pos) {
Pos temp_pos = { ori.x - 1, ori.y - 1 };
int q = n / 4, flag = DetQuadrant(ori, pos);
makeLTromino(flag, temp_pos);
if (n > 2) { // exit condition
for (int i = 0, t = 1;i < 2;i++) { // for next 4 squares(n -> n/2)
for (int j = 0; j < 2;j++, t++) {
Pos next_ori = ori;
Pos next_pos = { ori.x - 1, ori.y - 1 };
// new ori
if (i == 0) next_ori.x -= q;
else next_ori.x += q;
if (j == 0) next_ori.y -= q;
else next_ori.y += q;
// consider as 'X' in each quadrant
if (t != flag) {
next_pos.x += i; next_pos.y += j;
}
else next_pos = pos;
fill(n / 2, next_ori, next_pos);
}
}
}
}- ori: 한 변의 길이가 n인 정사각형의 중심 좌표
- pos: 해당 정사각형에서 채워진 사각형의 좌표
- 종료조건: 정사각형의 한 변의 길이가 2와 같거나 작으면 종료.
(n이 2일 경우 makeLTromino()를 실행하면 정사각형이 다 채워진다.
그러므로 더이상 분할할 필요가 없다.)
나머지의 경우, 한 변의 길이가 n일 때 makeLTromino()로 L-Tromino를 생성한다.
그 후 4번의 반복문을 통해 사각형을 4개로 분할하여 재귀적으로 수행한다.
- 초기 호출문
Pos init_pos = { x, y };
Pos init_ori = { n / 2, n / 2 };
fill(n, init_ori, init_pos); 💥 발전하자
- 개선점
- fill() 함수에서 next_ori와 next_pos를 구하는 과정이 비효율적이라는 생각이 든다.
조금 더 우아한 방법이 있을 것 같다.
