[ALGOSPOT] BOARDCOVER

🎯 ALGOSPOT - BOARDCOVER

🤔 私の答え

📌 質問する

- ALGOSPOT > BOARDCOVER

📌 名前の日付

2020.03.21

📌 試行回数

Failed

💡 Code

def solution():
    # 예외 처리 해주기
    if white_spaces % 3 != 0 or white_spaces < 3:
        return
 
    blocks = white_spaces // 3  # 필요한 블록(3개짜리 칸이 1개의 블록) 개수
 
    def board_cover(cur_r, cur_c, blocks):  # dfs
        global result
 
        # 종료 부분
        if blocks == 0:
            result += 1
            return
 
        # 조사 부분
        for r in range(row):
            for c in range(col):
                if board[r][c] == ".":
                    if r + 1 < row and c + 1 < col:
                        if board[r + 1][c] == "." and board[r][c + 1] == ".":  # ┌ 모양 칸 채우기
                            change_to_black(r, c, r + 1, c, r, c + 1)
                            board_cover(r, c + 1, blocks - 1)
                            change_to_white(r, c, r + 1, c, r, c + 1)
 
                        if board[r + 1][c] == "." and board[r + 1][c + 1] == ".":  # └ 모양 칸 채우기
                            change_to_black(r, c, r + 1, c, r + 1, c + 1)
                            board_cover(r, c + 1, blocks - 1)
                            change_to_white(r, c, r + 1, c, r + 1, c + 1)
 
                        if board[r][c + 1] == "." and board[r + 1][c + 1] == ".":  # ┐ 모양 칸 채우기
                            change_to_black(r, c, r, c + 1, r + 1, c + 1)
                            board_cover(r, c + 1, blocks - 1)
                            change_to_white(r, c, r, c + 1, r + 1, c + 1)
 
                    if c - 1 >= 0 and r + 1 < row:
                        if board[r + 1][c] == "." and board[r + 1][c - 1] == ".":  # ┘ 모양 칸 채우기
                            change_to_black(r, c, r + 1, c, r + 1, c - 1)
                            board_cover(r, c + 1, blocks - 1)
                            change_to_white(r, c, r + 1, c, r + 1, c - 1)
 
                    # "."를 지났는데 채워지지 않았으면 종료
                    if board[r][c] == ".":
                        return
 
    def change_to_black(i1, j1, i2, j2, i3, j3):
        board[i1][j1] = "#"
        board[i2][j2] = "#"
        board[i3][j3] = "#"
 
    def change_to_white(i1, j1, i2, j2, i3, j3):
        board[i1][j1] = "."
        board[i2][j2] = "."
        board[i3][j3] = "."
 
    board_cover(0, 0, blocks)
 
 
for _ in range(int(input())):
    row, col = map(int, input().split())
    white_spaces = 0
    board = []
    for i in range(row):
        b = input()
        board.append(list(b))
        for x in b:
            if x == ".":
                white_spaces += 1
 
    result = 0
    solution()
    print(result)

💡 トラブルシューティング方法

可能なブロックの形状にはこの3種類がある.(現在位置を現在としてマーク)

他に必要なブロックがない場合(block==0)、結果を1つ追加し、現在のナビゲーションを終了します.

答えを間違える理由

- 가능한 블록의 케이스가 4가지 있다는 것을 파악하기 어려웠다.
- 현재 탐색하고 있는 블록(board[r][c])을 지났는데 채워지지 않았다면 탐색을 종료하는 것을
제대로 처리해주지 않아서 오류가 났었다.

💡 新知

-