[파이썬으로 배우는 알고리즘 기초] 2. 분할 정복법 (3)

2-6. 트로미노 퍼즐

• 트로미노(tromino): 정사각형이 3개 붙어있는 것
• 가로와 세로로 m개의 정사각형이 연결되어 있는 바둑판이 있고, 이 바둑판의 1칸은 X 표시가 되어 있음(단, m은 2의 거듭제곱)
• 다음 조건을 만족하도록 트로미노를 바둑판 전체에 채우려고 함
  - X 표시가 되어 있는 칸은 채울 수 없음
  - 트로미노는 겹쳐 놓거나 바둑판 밖으로 빠져나가게 둘 수 없음
• 분할: 4개의 사분면으로 분할 후 X가 없는 사분면의 모서리 채우기
  정복: 채워진 4개의 사분면을 재귀 호출

import random

# 입력: M, X의 Row, X의 Col
M = 8
xrow = random.randint(0, M - 1)
xcol = random.randint(0, M - 1)
board = [[0] * M for _ in range(M)]
board[xrow][xcol] = -1
tromino_cnt = 0

def fillCenterExcept(board, mrow, mcol, N): # N사분면 제외하고 나머지 사분면의 모서리에 X를 추가
    global tromino_cnt

    tromino_cnt += 1
    if N != 1:
        board[mrow - 1][mcol] = tromino_cnt
    if N != 2:
        board[mrow - 1][mcol - 1] = tromino_cnt
    if N != 3:
        board[mrow][mcol - 1] = tromino_cnt
    if N != 4:
        board[mrow][mcol] = tromino_cnt

def tromino(board, srow, scol, size, xrow, xcol):
    if size == 1:
        return
    else:
        mrow = srow + (size // 2) # middle of row
        mcol = scol + (size // 2)
        xrow1, xcol1 = mrow - 1, mcol     # 1사분면에 추가할 X의 위치
        xrow2, xcol2 = mrow - 1, mcol - 1 # 2사분면에 추가할 X의 위치
        xrow3, xcol3 = mrow, mcol - 1     # 3사분면에 추가할 X의 위치
        xrow4, xcol4 = mrow, mcol         # 4사분면에 추가할 X의 위치

        # 이미 X가 있는 사분면은 제외
        if xrow < mrow and xcol >= mcol:
            fillCenterExcept(board, mrow, mcol, 1)
            xrow1, xcol1 = xrow, xcol
        elif xrow < mrow and xcol < mcol:
            fillCenterExcept(board, mrow, mcol, 2)
            xrow2, xcol2 = xrow, xcol
        elif xrow >= mrow and xcol < mcol:
            fillCenterExcept(board, mrow, mcol, 3)
            xrow3, xcol3 = xrow, xcol
        elif xrow >= mrow and xcol >= mcol:
            fillCenterExcept(board, mrow, mcol, 4)
            xrow4, xcol4 = xrow, xcol

        tromino(board, srow, mcol, size // 2, xrow1, xcol1)
        tromino(board, srow, scol, size // 2, xrow2, xcol2)
        tromino(board, mrow, scol, size // 2, xrow3, xcol3)
        tromino(board, mrow, mcol, size // 2, xrow4, xcol4)

# 출력: 각 트로미노에 번호를 부여하여 빈 칸 채우기
tromino(board, 0, 0, M, xrow, xcol)
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()

 

 

 

※ 강의 링크: https://inf.run/v8Rn