[python] algospot boardcover 문제 풀이

문제 

HxW 크기의 게임판이 주어진다. 게임판은 흰 칸과 검은 칸으로 구성된 격자 모양을 하고 있다.

세 칸짜리 L자 모양의 블록을 이용해 게임판의 흰 영역을 모두 블록으로 덮고 싶다.

이때 L자 블록은 마음대로 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 밖으로 나가서는 안된다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하시오

-> 문제 링크 : https://algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

 

문제 풀이

이 문제는 부분문제로 쪼갤 수 있다.

현재 문제인 흰 공간 x를 채우는 문제는 적절한 위치에 블록이 들어가고 남은 흰 공간 x-3를 채우는 문제로 쪼개진다.

그리고 기저사례 즉, 문제가 끝나는 시점은 모든 칸이 검정으로 덮어지는 경우가 된다.

 

문제가 쪼개지는 것을 확인했으니 블록을 채우는 방법을 생각하면 된다.

L 모양 블록을 이용해 하나의 흰 칸을 채우는 방법의 수는 4가지가 된다.

그런데 모든 흰색 공간에 놓을 수 있다고 가정한다면 최대 50개의 흰색 공간 위치가 있기에, 대략 O(200^n)이 된다. 

이런 방식으로 재귀를 짜게되면 시간초과가 발생하여 문제를 풀지 못한다.

 

하지만 이 문제는 게임판을 덮는 방법의 수를 찾는 문제이기에 블록을 놓는 순서와는 상관이 없다.

그러면 우리는 블록이 놓이는 순서를 강제해도 상관이 없게 된다.

만약 우리가 항상 좌측 상단에 있는 흰 공간을 먼저 채운다고 가정을 하면 놓는 위치는 고정되고,

L 블록의 놓는 방향에 따라서만 달라지기에  방법의 수는 4개로 줄어든다.

시간복잡도 O(4^n)으로 해결되는 문제이고 가로와 세로의 길이가 최대 16이다. 

하지만 실제로 계산을 해보면 여러 제약 때문에 훨씬 빠른 시간 안에 계산이 가능하다.

 

문제를 풀기 위해 firstEmpty, checkBlock, fillBlock, removeBlock, countBlock 함수를 구현했다.

 

* firstEmpty() : 게임판을 보고 항상 좌측 상단에 있는 흰 공간의 x,y 좌표를 반환한다.

* checkBlock(x,y,num) : x,y 공간을 num번 모양의 L자 블록으로 덮을 수 있는지 여부를 반환한다.

* fillBlock(x,y,num) : x,y 공간을 num번 모양의 L자 블록으로 덮는다.

* removeBlock(x,y,num) : x,y 공간을 덮은 num번 모양의 L자 블록을 지운다.

* countBlock() : 재귀를 돌면서 계속해서 현재 문제를 해결한다. 좌측 상단의 흰 공간 x,y를 찾아내고 그 위치를 덮을 수 있는 블록이 나오면 덮은 뒤 다시 재귀를 호출하여 쪼개진 부분문제로 진입한다. 이를 모든 게임판이 덮어진 기저사례까지 반복하여 문제를 해결한다.   

 

 

코드

import sys

# 1개
N = int(sys.stdin.readline().rstrip())
move = [[(0,0),(0,1),(1,0)], [(0,0),(0,1),(1,1)], [(0,0),(1,0),(1,1)], [(0,0),(1,0),(1,-1)]]


def firstEmpty() :
    for x in range(H) :
        for y in range(W) :
            if matrix[x][y] == '.' :
                return x,y

    return -1,-1

def checkBlock(x,y,num) :

    for dx,dy in move[num] :

        nx = x+dx
        ny = y+dy

        if not (0 <= nx < H and 0 <= ny < W) :
            return False

        if matrix[nx][ny] == '#' :
            return False

    return True

def fillBlock(x,y,num) :

    for dx,dy in move[num] :
        nx = x+dx
        ny = y+dy
        matrix[nx][ny] = '#'

def removeBlock(x,y,num) :

    for dx, dy in move[num]:
        nx = x + dx
        ny = y + dy
        matrix[nx][ny] = '.'


def countBlock() :

    x,y = firstEmpty()

    if  x is -1 and y is -1 :
        return 1

    ret = 0

    for m in range(len(move)) :
        if checkBlock(x,y,m) :
            fillBlock(x,y,m)
            ret += countBlock()
            removeBlock(x,y,m)

    return ret

for _ in range(N) :

    H,W = map(int, sys.stdin.readline().rstrip().split(" "))
    matrix = []

    for _ in range(H) :
        matrix.append(list(sys.stdin.readline().rstrip()))

    emptyCount =  0
    for row in range(H) :
        for col in range(W) :
            if matrix[row][col] == '.' :
                emptyCount+=1

    if emptyCount % 3 == 0 :
        print(countBlock())

    else :
        print("No")

 

초기 접근 방식과 오답의 원인

처음 문제를 접했을 때 하나의 흰 공간을 채우는 방법의 수가 12가지라고 생각했고 시간 초과가 발생할 것이라고 생각했다.

모든 방법의 수를 따질 때는 순서를 강제하여도 문제가 변하지 않는다는 사실을 알지 못해 문제풀이에 어려움을 겪었다.