트로미노 알고리즘을 분할정복법으로 해결하는 방법!

트로미노(Tromino)는 2^k x 2^k 크기의 체스판에서 1칸을 제외한 모든 칸이 채워져 있을 때, 그 빈 칸을 1칸의 직사각형 모양 블록으로 덮는 문제입니다.

분할정복법을 사용하여 트로미노 알고리즘을 구현하려면, 큰 문제를 작은 문제로 분할하고, 작은 문제에서 구한 해결책을 이용해 큰 문제의 해결책을 찾아가는 과정이 필요합니다. 아래는 분할정복법을 이용한 트로미노 알고리즘 구현 예시입니다.

문제 분할
체스판을 4개의 크기가 같은 사각형으로 분할합니다.
빈 칸이 포함된 사각형에는 임의의 위치에 1칸의 직사각형 모양 블록을 놓습니다.
기저 조건
분할한 사각형의 크기가 2x2가 될 때까지 계속 분할합니다.
작은 문제 해결
2x2 크기의 사각형에서는 빈 칸을 찾아 해당 위치에 1칸의 직사각형 모양 블록을 놓습니다.
해 결
분할한 사각형에서 놓인 블록을 이용해 큰 사각형에 블록을 놓습니다.
위와 같은 분할정복법으로 트로미노 알고리즘을 구현할 수 있습니다. 하지만 이 방법은 최적해를 보장하지는 않습니다. 또한, 체스판의 크기가 2^k x 2^k가 아닌 경우에는 이 방법이 적용되지 않습니다. 따라서 보다 효율적인 트로미노 알고리즘을 찾는 것이 중요합니다.