[AlgoSpot][Python] 게임판 덮기

📒 문제 설명

🔖 https://www.algospot.com/judge/problem/read/BOARDCOVER

📖 문제
H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.

✍ 입력
입력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, . 는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.

💻 출력
한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

---

✏️ 풀이 과정

📝 접근

• 블럭을 놓는 순서만 다른 경우를 중복해서 카운트하는 것을 방지하기 위해 블럭은 가장 위에서 왼쪽부터 채워진다고 가정한다.
  따라서 cover_type에서 블럭의 현재 위치 [0, 0]보다 위쪽에 있거나 바로 왼쪽에 위치한 블럭은 고려하지 않아도 된다.
  다음 그림은 블럭의 현재 위치(노란 블럭)에 대해 표현한 cover_type이다.

• 전체 흰 블럭의 개수가 3의 배수가 아닌 경우, 모든 흰 블럭을 L자 블럭으로 채울 수 없으므로 0을 반환한다.

• setBlock 함수의 delta가 1인 경우, 검은 블럭으로 채우고, -1인 경우에는 흰 블럭으로 채운다.

• findNext 함수에서 -1을 반환하는 경우, 남은 흰 블럭이 없는 것이다. 따라서, recursiveCover 함수에서 next_y의 값이 -1이면, ans가 1 증가한다.

✨ 소스 코드

import sys
input = sys.stdin.readline

WHITE = 0
BLACK = 1

cover_type = [
    [[0, 0], [1, 0], [0, 1]],
    [[0, 0], [0, 1], [1, 1]],
    [[0, 0], [1, 0], [1, 1]],
    [[0, 0], [1, 0], [1, -1]]
]

def isValidBlock(y, x, board_height, board_width):
    return 0 <= y < board_height and 0 <= x < board_width

def boardCover(board):
    ans = 0

    white_count = sum(row.count(WHITE) for row in board)
    if white_count % 3 != 0:
        return ans

    def canCover(y, x, type):
        for i in range(3):
            ny, nx = y + cover_type[type][i][0], x + cover_type[type][i][1]
            if not isValidBlock(ny, nx, board_height, board_width) or board[ny][nx] != WHITE:
                return False
        return True

    def setBlock(y, x, type, delta):
        for i in range(3):
            ny, nx = y + cover_type[type][i][0], x + cover_type[type][i][1]
            board[ny][nx] += delta

    def findNext(y, x):
        while y < board_height:
            while x < board_width:
                if board[y][x] == WHITE:
                    return y, x
                x += 1
            x = 0
            y += 1
        return -1, -1

    def recursiveCover(y, x):
        nonlocal ans
        next_y, next_x = findNext(y, x)
        if next_y == -1:
            ans += 1
            return
        for type in range(4):
            if canCover(next_y, next_x, type):
                setBlock(next_y, next_x, type, 1)
                recursiveCover(next_y, next_x)
                setBlock(next_y, next_x, type, -1)

    recursiveCover(0, 0)
    return ans

C = int(input())

for _ in range(C):
    board_height, board_width = map(int, input().split())
    board = [[BLACK if c == '#' else WHITE for c in input().rstrip()]
             for _ in range(board_height)]
    print(boardCover(board))