[알고스팟/종만북/완전탐색/재귀] 게임판 덮기(Python)

문제

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

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

입력

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

출력

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

예제 입력

3 3 7 #.....# #.....# ##...## 3 7 #.....# #.....# ##..### 8 10 ########## #........# #........# #........# #........# #........# #........# ##########

예제 출력

0 2 1514

출처 : https://www.algospot.com/judge/problem/read/BOARDCOVER

[접근]

1. 문제 단순화/순서 강제 ⇒ 왼쪽 상단부터 검사한다는 순서강제
2. 왼쪽상단부터 비어있는 칸을 찾아내서 검사
3. 편의를 위해 데이터 전처리(리스트화, 숫자화)
4. 블록방향의 경우, 상대적 위치를 정해두고 타겟 위치에 따라 검사진행
5. dfs 사용

[주의사항]

1. 파이썬의 경우, 다중 for문에서 한꺼번에 break하는 기능이 없음⇒ flag사용해서 상위 for문 break해주는 기법 사용
2. 파이썬은 기본 recursion limit이 10**3이므로, 재귀 사용 시에 limit 풀어주기

[기타 참고사항]

1. 처음에 is_fulfilled함수를 따로 빼서 검사를 해주었는데, 책처럼 빈칸을 찾는 완전탐색에서 찾지 못하면 fulfilled로 간주하는 것이 더 효율적
2. 파이썬 다중for문에서 break를 걸 때는 항상 주의하자!

import sys
sys.setrecursionlimit(10**6)

L_type = [[(1, 0), (1, 1)], [(0, 1), (1, 1)], [(1, 0), (1, -1)], [(1, 0), (0, 1)]]

new_board = []
for i in range(H):
    temp = board[i].replace('#', '1')
    temp = temp.replace('.', '0')
    new_board.append(list(map(int, temp)))

def dfs(new_board, L_type, H, W):
    ret = 0
    startH = -1
    startW = -1
    #다중 for문 break를 위한 flag처리
    flag = False
    for h in range(H):
        for w in range(W):
            if new_board[h][w] == 0:
                #빈칸찾으면 변수 지정해주고 멈추기
                startH = h
                startW = w
                flag = True
                break
        if flag: break
    #변수가 지정되지 않았다는 것은 모두 채워졌다는 의미이므로 return
    if startH == -1 and startW == -1: return 1
    for i in range(4):
        h1 = startH + L_type[i][0][0]
        w1 = startW + L_type[i][0][1]
        h2 = startH + L_type[i][1][0]
        w2 = startW + L_type[i][1][1]
        if 0<= h1 < H and 0<= h2 < H and 0<= w1 < W and 0<= w2 < W and new_board[h1][w1] == 0 and new_board[h2][w2] == 0:
            new_board[h1][w1] = 1
            new_board[h2][w2] = 1
            new_board[h][w] = 1
            ret += dfs(new_board, L_type, H, W)
            new_board[h1][w1] = 0
            new_board[h2][w2] = 0
            new_board[h][w] = 0
    return ret

print(dfs(new_board, L_type, H, W))