트로미노 타일

트로미노 타일

이해하는데 너무 오랜 시간이 걸렸다. 두고두고 봐야할 코드인 것 같다.
코드를 뜯어보면서 공부해보자.

# 정사각형 영역이 비어있는지 확인하는 함수
def check(x, y, size):
    for nx in range(x, x + size):
        for ny in range(y, y + size):
            if result[nx][ny] != 0:
                return False
    return True

# 그리드를 나누고 채우는 재귀 함수
def divide_and_fill(x, y, size):
    global numbers
    numbers += 1
    next_size = size // 2
    # 각 영역의 중간 위치 계산
    input_position = [[x + next_size - 1, y + next_size - 1], [x + next_size, y + next_size - 1],
                      [x + next_size - 1, y + next_size], [x + next_size, y + next_size]]
    # 각 영역을 채우고 중간 위치에 숫자 할당
    for ind, val in enumerate([[x, y], [x + next_size, y], [x, y + next_size], [x + next_size, y + next_size]]):
        sx, sy = val
        input_x, input_y = input_position[ind]
        # 해당 영역이 비어있으면 숫자 할당
        if check(sx, sy, next_size):
            result[input_x][input_y] = numbers

    if size == 2:
        return
    # 영역을 나누어 재귀 호출
    divide_and_fill(x, y, next_size)
    divide_and_fill(x + next_size, y, next_size)
    divide_and_fill(x, y + next_size, next_size)
    divide_and_fill(x + next_size, y + next_size, next_size)

k = int(input())  # 입력값 k를 받음
N = 2 ** k  # 그리드의 크기 계산 (2의 k제곱)
input_x, input_y = map(int, input().split())
# 0-based 인덱스로 변환
x = input_y - 1
y = input_x - 1
# 결과 그리드 초기화
result = [[0 for _ in range(N)] for _ in range(N)]
# 시작 위치 표시
result[x][y] = -1

numbers = 0  # 숫자 초기화
divide_and_fill(0, 0, N)  # 그리드를 나누고 채우는 함수 호출

# 결과 출력
for row in result:
    print(*row)

정사각형 영역이 비어있는지 확인하는 함수

def check(x, y, size):
    for nx in range(x, x + size):
        for ny in range(y, y + size):
            if result[nx][ny] != 0:
                return False
    return True

x좌표와 y좌표, 정사각형의 한 변의 길이를 입력받고, 하나라도 0이 아니면 False를 리턴하는 함수이다.
즉, 비어있으면 True, 하나라도 채워져있으면 False

네 구역으로 나누고 타일을 채우는 재귀 함수

def divide_and_fill(x, y, size):
    global numbers
    numbers += 1
    next_size = size // 2
    # 각 영역의 중간 위치 계산
    input_position = [[x + next_size - 1, y + next_size - 1], [x + next_size, y + next_size - 1],
                      [x + next_size - 1, y + next_size], [x + next_size, y + next_size]]
    # 각 영역을 채우고 중간 위치에 숫자 할당
    for ind, val in enumerate([[x, y], [x + next_size, y], [x, y + next_size], [x + next_size, y + next_size]]):
        sx, sy = val
        input_x, input_y = input_position[ind]
        # 해당 영역이 비어있으면 숫자 할당
        if check(sx, sy, next_size):
            result[input_x][input_y] = numbers

    if size == 2:
        return
    # 영역을 나누어 재귀 호출
    divide_and_fill(x, y, next_size)
    divide_and_fill(x + next_size, y, next_size)
    divide_and_fill(x, y + next_size, next_size)
    divide_and_fill(x + next_size, y + next_size, next_size)

여기도 마찬가지로, x좌표와 y좌표, 정사각형의 한 변의 길이를 입력받는다.

여기서 조금 복잡한데, input_position은 가운데 네 개의 점을 의미하고,
for문에서 각 네 영역의 우측 상단에 해당하는 점들을 기준으로 check()함수를 이용하여 True 여부를 판단하고, 그 타일에 해당하는 input_position에 numbers를 칠하는 방식이다.
이 부분도 여러번 보고 직접 해보면서 감을 익혀야겠다.

이렇게 다 칠했는데 size가 2였으면 리턴해준다.

이후 영역을 나누어 다시 divide_and_fill()함수를 재귀호출 해준다.