[분할 정복] 파이썬 트로미노(tromino) 타일링 알고리즘

트로미노(tromino)

트로미노(tromino)는 크기가 같은 정사각형 3개를 이어붙여 만든 다각형을 말한다. 트로미노는 아래의 2종류가 있다.

우리가 오늘 문제에서 사용할 트로미노는 왼쪽의 계단 형 트로미노이다.   

 

트로미노 타일링 문제를 해결하기 위해서는 분할정복 기법을 사용할 수 있다. 

 

1. 분할정복 (Divide & Conquer)

분할 정복은 Recursion 기반의 해결기법이다. 분할정복 기법의 문제 해결 시나리오는 다음과 같다. 

1. 분할(Divide) : 주어진 문제를 두 개 혹은 그 이상의 같은 형식의 작은 문제로 나눈다. 
2. 정복 (conquer) : 나누어진 작은 문제는 재귀적으로 해결한다. 즉, 나누어진 작은 문제는 더 이상 나누어서 문제를 해결할 필요가 없이 직접 문제를 해결할 수 있을 때 까지 재귀적으로 계속 분할해가면서 문제를 해결한다. 
3. 통합(combine) : 한개 이상의 작은 문제들로부터 구한 모든 해답들을 서로 통합해서 원래 문제의 해답을 만든다. 

 

분할정복기법은 Top-Down 문제해결방법이라고 할 수 있다. 

초기에 큰 문제가 주어졌을 때, 직접 이 문젤르 해결할 수 없으므로, 이 문제를 적절한 크기의 작은 문제로 분할하여 해결하는 방법이다. 이런 방법을 top-down 방법이라고 한다. 

 

Top-down 방법으로 분할된 작은 문제들은 직접 문제를 해결할 수 없는 경우 또 다시 더 작은 문제로 분할 된다. 작은 문제는 문제를 직접 해결할 수 있을 때 까지 계속 분할한다. 이러한 해결방법은 recursion으로 쉽게 구현할 수 있다. 

 

분할정복기법 알고리즘의 정확성은 수학적 귀납법을 사용해 증명가능하다. 

 

2. 수학적 귀납법으로 분할정복 증명하기 

수학적 귀납법은 다음 3단계로 이루어진다. 

1. Base Step 
2. Inductive hypothesis
3. Inductive Step

트로미노 타일을 예시로 수학접 귀납법에 의한 증명을 설명한다면 다음과 같다. 

1)Base case : n = 1인 경우 

한쪽이 떨어져나간 2x2 크기의 격자판은 1개의 트로미노 타일로 채울 수 있다. 

 

2) Inductive Hypothesis : n = k인 경우

한쪽이 떨어져나간 2^kX2^k크기의 격자판은 항상 트로미노 타일로 채울 수 있다라고 가정한다. 

 

3) Inductive step : n = k+1인 경우 

  2)번 단계의 가정을 이요하여 한쪽이 떨어져나간 2^(k+1)X2^(k+1) 크기의 격자판은 다음과 같이 트로미노 타일로 채울 수 있다라고 증명할 수 있다. 

결론 : 따라서 모든 2^nX2^n (n>=1)크기의 격자판은 위 알고리즘에 따라 트로미노로 채울 수 있다. 

 

 

3. 코드로 구현하기 

 

입력 

테스트케이스 n , 보드의 크기, 보드의 빈공간 좌표(i,j)

(보드의 크기는 항상 2의 n제곱)

 

출력

타일을 채운 보드판 출력

 

이제 분할정복 기법을 사용해서 트로미노 문제를 코드로 구현해 보자. 개인적으로 트로미노를 코드로 구현하기 위해 컨셉을 이해하는데 상당히 오래걸렸다 ㅠ  그래서 코드 구현을 하기위한 컨셉을 쉽게 설명해보려고 한다. 

먼저 우리는 문제를 한번에 해결하지 않고 분할 정복으로 해결할 것이다. 

보드를 가로, 세로로 반절 나누면 

 

트로미노문제를 해결하기 위해 두가지 함수를 구현했다. 

• tromino : 재귀적으로 호출하는 트로미노 함수 
• fillTile :  트로미노 타일을 채우는 함수 

def tromino(board, size, srow, scol, xrow, xcol):
    # 기저 조건
    if (size ==1 ):
        return 

    # board의 중앙값 구하기 
    mrow, mcol = srow + (size//2), scol + (size//2)

    # 1, 2, 3, 4 사분면의 빈공간을 미리 예측
    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사분면
        fillTile(board, mrow, mcol,  1)
        xrow1, xcol1 = xrow, xcol
    elif xrow < mrow and xcol >= mcol : # 2사분면
        fillTile(board, mrow, mcol, 2)
        xrow2, xcol2 = xrow, xcol
    elif xrow >= mrow and xcol < mcol : # 3사분면
        fillTile(board, mrow, mcol, 3)
        xrow3, xcol3 = xrow, xcol
    elif  xrow >= mrow and xcol >= mcol : # 4사분면
        fillTile(board, mrow, mcol, 4)
        xrow4, xcol4 = xrow, xcol

    # 각 사분면 분할 
    tromino(board, size//2, srow, scol, xrow1, xcol1) # 1사분면
    tromino(board, size//2, srow, mcol, xrow2, xcol2) # 2사분면
    tromino(board, size//2, mrow, scol, xrow3, xcol3) # 3사분면
    tromino(board, size//2, mrow, mcol, xrow4, xcol4) # 4사분면


# 타일 채우는 함수 
def fillTile(board, mrow, mcol, part):
    global count 
    count += 1
    if part !=1 :
        board[mrow-1][mcol-1] = count
    if part !=2 :
        board[mrow-1][mcol] = count
    if part !=3 :
        board[mrow][mcol-1] = count
    if part !=4 :
        board[mrow][mcol] = count

# 테스트 
test_case = int(input())
for _ in range(test_case):
    # 입력값 받기 
    size = int(input())
    xrow, xcol = map(int, input().split())

    # 격자판 만들기 
    board = [[-1] * size for _ in range(size)]
    board[xrow][xcol] = 0 # 비어있는 체스판 
    count = 0
    tromino(board, size, 0, 0, xrow, xcol)
    for row in board : 
        print(' '.join(map(str, row)))