분할정복과 트로미노 퍼즐

문제정의

트로미노 퍼즐이란 정사각형이 3개 붙어있는것을 말한다. 가로와 세로로 m 개의 정사각형이 연결되어있고 여기서 m 은 2의 거듭제곱이라 가정한다. 이에 다음 조건을 만족하도록 트로미노를 바둑판에 채워야 한다

조건
⁃ X 표시가 되어 있는 칸은 트로미노로 덮을 수 없다.
⁃ 트로미노는 겹쳐 놓을 수 없다.
⁃ 트로미노는 바둑판 바깥으로 삐져나올 수 없다.
⁃ 바둑판 전체를 트로미노로 채워야 한다.

말로 하면 좀 이해가 어려울 수 있다. 다음의 링크를 통해 직접 해보면서 익혀보면 이해가 더 쉬울것이라 생각한다

보통 함수에서 1사분면이라 함은 우상단부터 반시계방향으로 2 3 4로 진행되지만, 이 문제에서는 좌상단을 1사분면이라 지칭하고 시계방향으로 2 3 4 로 진행한다

그래서 무엇을 해결해야 하는가?

다음과 같은 4 * 4 의 정사각형이 있다고 하자.
여기에 하나의 빈칸 x를 부여하고, 나머지를 3개의 트로미노로 채우면 된다.

여기서 우리가 주목해야 할 사실은 정사각형이 모두 2의 거듭제곱크기라는 것이다.
즉, 분할정복을 통해 정사각형은 더 작은 정사각형으로 나누고, 이 과정을 반복 가장 작은 단위 정사각형인 2*2부터 만들어가며 하나씩 키워나가면 되는것이다.

코드를 보면서 설명을 하도록 하겠다.

코드

def tromino(board, srow, scol, size, xrow, xcol):
    if (size == 1):
        return
    else:
        mrow = srow + (size // 2) # 중간 row
        mcol = scol + (size // 2) # w중간 col
        xrow1, xcol1 = mrow - 1, mcol - 1 
        xrow2, xcol2 = mrow - 1, mcol
        xrow3, xcol3 = mrow, mcol - 1
        xrow4, xcol4 = mrow, mcol
        # 각각의 사사분면으로 나눠줌 

    if (xrow < mrow and xcol < mcol):  # 1사분면
        fillCenterExcept(board, mrow, mcol, 1)
        xrow1, xcol1 = xrow, xcol
    elif (xrow < mrow and xcol >= mcol):  # 2사분면
        fillCenterExcept(board, mrow, mcol, 2)
        xrow2, xcol2 = xrow, xcol
    elif (xrow >= mrow and xcol < mcol):  # 3사분면
        fillCenterExcept(board, mrow, mcol, 3)
        xrow3, xcol3 = xrow, xcol
    elif (xrow >= mrow and xcol >= mcol):  # 4사분면
        fillCenterExcept(board, mrow, mcol, 4)
        xrow4, xcol4 = xrow, xcol
    tromino(board, srow, scol, size // 2, xrow1, xcol1)
    tromino(board, srow, mcol, size // 2, xrow2, xcol2)
    tromino(board, mrow, scol, size // 2, xrow3, xcol3)
    tromino(board, mrow, mcol, size // 2, xrow4, xcol4)
    # 재귀함수형태를 통해 각 정사각형을 더 작은 단위로 나눔 

이 코드는 정사각형은 분할하고 fillCenterExcept를 호출, 각 정사각형에 맞는 칸을 채우도록 하는 함수이다.

def fillCenterExcept(board, mrow, mcol, part):
    global tromino_count
    tromino_count += 1
    if (part != 1):
        board[mrow - 1][mcol - 1] = tromino_count
    if (part != 2):
        board[mrow - 1][mcol] = tromino_count
    if (part != 3):
        board[mrow][mcol - 1] = tromino_count
    if (part != 4):
        board[mrow][mcol] = tromino_count

카운트를 통해서 어떤 칸에 어떤 트로미노가 들어갔는지 기록하는 함수이다. part는 현재의 사분면을 의미한다.

def print_board(board):
    for i in range(m):
        for j in range(m):
            if (board[i][j] < 0):
                print("%3s"%"X", end="")
            else:
                print("%3d"%board[i][j], end="")
        print()

import random
m = 4
xrow = random.randint(0, m-1)
xcol = random.randint(0, m-1)
print(xrow, xcol)
board = [[0] * m for _ in range(m)]
board[xrow][xcol] = -1
tromino_count = 0
tromino(board, 0, 0, m, xrow, xcol)
print_board(board)

그 후, 작성된 이중리스트를 출력하는 코드와 보드에 x 칸을 랜덤하게 생성하는 코드를 작성한다.
실행하면,

다음과 같은 결과가 출력된다.

실행방식 생각해보기

1. 우선 1,0 자리에 x 가 생성되었다.
2. 그 후, srow s col인 1 0 은 mrow mcol 보다 작았기에 x 가 1사분면에 있다고 판단하였고 fillCenter 함수에 따라 2 3 4 분면에서 한칸씩을 숫자 1로 채워놓게 되었다.
3. 그 후 함수에 따라 1 2 3 4 분면을 더 작은 정사각형으로 분할하고, 그 정사각형 역시 위와 동일한 과정으로 빈칸들을 채워나가면 다음과 같은 그림이 완성된다.

다른 경우

8*8 의 경우이다.
퍼즐문제라고 생각하고 풀어보면 꽤 재미있다