문제정의
트로미노 퍼즐이란 정사각형이 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,0 자리에 x 가 생성되었다.
- 그 후, srow s col인 1 0 은 mrow mcol 보다 작았기에 x 가 1사분면에 있다고 판단하였고 fillCenter 함수에 따라 2 3 4 분면에서 한칸씩을 숫자 1로 채워놓게 되었다.
- 그 후 함수에 따라 1 2 3 4 분면을 더 작은 정사각형으로 분할하고, 그 정사각형 역시 위와 동일한 과정으로 빈칸들을 채워나가면 다음과 같은 그림이 완성된다.
다른 경우
8*8 의 경우이다.
퍼즐문제라고 생각하고 풀어보면 꽤 재미있다
