[알고스팟]BOARDCOVER

문제

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

입력

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

출력

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

---

풀이

• L자블럭은 회전가능하다는 조건에서 총 4가지의 모양이 될 수 있다.
• 
• 가장 중요한 조건은 좌측최상단은 꼭 채워진 칸이어야 한다. 이를 만족하는 4가지 L자 블럭의 좌표는 다음과 같다.
  • [(x,y),(x+1,y),(x+1,y+1)]
  • [(x,y),(x+1,y),(x,y+1)]
  • [(x,y),(x,y+1),(x+1,y+1)]
  • [(x+1,y-1),(x+1,y),(x,y)]

• 모든 칸을 순서대로 탐색하며 L자 블럭이 들어갈 수 있는 곳에 끼웠다 뺐다를 반복하며 모든 경우를 탐색한다.

  • 하나를 끼운후 해당상태에서 다음칸을 재귀로 호출한 후 해당 조건이 끝이나면 블럭을 제거하고 다음 조건을 진행한다.

  • 재귀를 끝내는 조건은 다음과 같다

    • 모든 칸의 탐색이 끝난경우
    • 현재칸의 좌측상단 칸이 채워지지 않은 경우
      -> 이후에도 채워질 수 없는 상태로 더 탐색할 필요X
    • 모든 칸이 채워진 경우
      -> 이 경우에는 count

코드

import sys
testcase = int(sys.stdin.readline())

for t in range(testcase):
    h,w=map(int,sys.stdin.readline().split())

    board = [[] for i in range(h)]
    global white
    white = 0
    usable=[]

    for i in range(h):
        tmp = sys.stdin.readline()
        for j in range(w):
            if tmp[j]=='#':
                board[i].append(1)
            else:
                board[i].append(0)
                white+=1
            usable.append((i,j))

    answer = []

    def dfs(index,white):
        if index == len(usable):
            return
        
        x = usable[index][0]
        y = usable[index][1]
    
        if x>0 and y>0 and board[x-1][y-1]==0:
            return
        
        if white == 0:
            answer.append(0)
            return 1

        if x<h-1 and y<w-1 and board[x][y]==0 and board[x+1][y]==0 and board[x+1][y+1]==0:
            board[x][y]=2
            board[x+1][y]=2
            board[x+1][y+1]=2
            white-=3
            dfs(index+1,white)
            board[x][y]=0
            board[x+1][y]=0
            board[x+1][y+1]=0
            white+=3
        if x<h-1 and y<w-1 and board[x][y]==0 and board[x][y+1]==0 and board[x+1][y]==0:
            board[x][y]=2
            board[x][y+1]=2
            board[x+1][y]=2
            white-=3
            dfs(index+1,white)
            board[x][y]=0
            board[x][y+1]=0
            board[x+1][y]=0
            white+=3
        if x<h-1 and y<w-1 and board[x][y]==0 and board[x][y+1]==0 and board[x+1][y+1]==0:
            board[x][y]=2
            board[x][y+1]=2
            board[x+1][y+1]=2
            white-=3
            dfs(index+1,white)
            board[x][y]=0
            board[x][y+1]=0
            board[x+1][y+1]=0
            white+=3
        if x<h-1 and y>0 and board[x][y]==0 and board[x+1][y-1]==0 and board[x+1][y]==0:
            board[x][y]=2
            board[x+1][y-1]=2
            board[x+1][y]=2
            white-=3
            dfs(index+1,white)
            board[x][y]=0
            board[x+1][y-1]=0
            board[x+1][y]=0
            white+=3
        
        dfs(index+1,white)

           

    dfs(0,white)
    print(len(answer))