[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)

💡 문제 해결 방법

1. 가능한 블록의 모양은 이렇게 3가지이다. (현재 위치를 '현재'라고 표시)
   
2. 왼쪽 → 오른쪽, 위쪽 → 아래쪽으로 이동하면서 현재 블록에 대하여 위의 4가지 경우가 가능한지 차례대로 비교해본다.
3. 그러나 현재 위치가 board[r][c]일 때 board[r][c]를 지났는데 채워지지 않았다면 이 케이스는 더 검사할 필요 없이 탐색을 종료한다.
   • 왜냐하면 가능한 블록의 모양에서 알 수 있듯이 이미 지나간 칸을 채우는 블록의 모양은 존재하지 않는다.
4. 만약 더 필요한 블록이 없을 때(block == 0) result를 1 추가하고 현재 탐색을 종료한다.
   

❌ (한번에 맞추지 못한 경우) 오답의 원인

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

💡 새롭게 알게 된 점

-

---