6.5 문제 : 게임판 덮기(Python)

문제 출처 : algospot.com :: BOARDCOVER

algospot.com :: BOARDCOVER

---

1. 내가 생각한 문제 접근 방법

(1) 게임판에 들어가는 블록은 3칸으로 구성되어있다.

• 3개의 변수에 대해 각 칸에 대한 좌표를 저장
• 반복문을 통해 회전 시키고 각 칸에 대응하는 보드판이 비어있으면 블록 설치
• 하지만, 블록을 회전시키는 방법에 대해 고안하지 못했다.

(2) 재귀적 호출을 통해 블록을 설치하고 해체하는 과정을 반복한다.

• 기저 사례를 찾고 기저 사례에서 경우의 수를 반환하여 누적
• 하지만, 재귀 호출을 어떤 방식으로 진행할지 고안하지 못했다.

2. 해설 풀이 방법

(1) 블록이 나올 수 있는 모양을 상대적인 리스트로 표현함

• 이 방법을 통해 블록을 회전시켰을 때, 현재 블록의 위치에서 리스트에 저장된 상대적인 인덱스를 더하고 빼는 과정으로 블록 모양을 지정할 수 있다.

# 블록의 모양을 상대적인 인덱스로 표현
block_type = [[(0, 0), (1, 0), (0, 1)],
              [(0, 0), (0, 1), (1, 1)],
              [(0, 0), (1, 0), (1, 1)],
              [(0, 0), (1, 0), (1, -1)]]

 

(2) 블록 설치 가능 여부를 반환하는 함수 : setBlock()

• 매개변수 t : 현재 블록의 모양, 반복문을 3번 도는데 각 블록의 칸에 대한 위치를 지정
• 매개변수 delta : 블록을 설치할 지, 제거할 지 결정
• 3개의 칸에 대해 반복문을 통과했다면 블록 설치 가능(True 반환)
• 반복문 도중 블록이 보드판의 범위를 넘어가거나 중복 설치되는 경우(False 반환)

# t : 블럭 모양
# delta : 현재 게임판에 블럭 설치 여부 결정(1 : 설치 / -1 : 제거)
def setBlock(board, r, c, t, delta):
    possible = True
    
    for i in range(3):
        nr = r + block_type[t][i][0]
        nc = c + block_type[t][i][1]

        if nr < 0 or nr >= h or nc < 0 or nc >= w:
            possible = False

        else:
            board[nr][nc] += delta
            
            # 값이 1이 넘어갈 경우 블록이 중복되어 설치되어있다고 간주
            if board[nr][nc] > 1:
                possible = False

    return possible

(3) 재귀적 호출을 통해 블록을 설치하는 함수 : cover()

• 블록의 좌상으로부터 우하로 빈 칸을 탐색하여 차례로 블록을 설치
• setBlock()을 통해 블록 설치 여부를 검사하고 설치가 가능한 경우 cover() 함수를 재귀적으로 호출
• 그리고 setBlock()의 delta 인수를 -1로 넘겨 블록 설치를 해제
• 위 과정을 반복하여 최종 누적된 result 값을 반환

def cover(board):
    h = len(board)
    w = len(board[0])

    # 아직 채워지지 않은 가장 위쪽 왼쪽에 있는 칸을 찾음
    r, c = -1, -1

    for i in range(h):
        for j in range(w):
            if board[i][j] == 0:
                r = i
                c = j
                break

        if r != -1:
            break

    # 기저 사례 : 모든 칸을 채웠으면 1을 반환
    if r == -1:
        return 1

    result = 0

    for t in range(4):
        # 게임판을 덮을 수 있는 경우, 재귀 호출을 통해 반복
        if setBlock(board, r, c, t, 1):
            result += cover(board)

        # 설치한 블럭 제거
        setBlock(board, r, c, t, -1)

    return result

 

(4) 문제 입-출력

for tc in range(int(input())):
    h, w = map(int, input().split())
    
    board = []
    for i in range(h):
        board.append(list(map(int, input().split())))

    print(cover(board))

3. 후기

  처음 문제를 봤을 때 '문제를 어떻게 해결해야겠다.' 라는 해결방법은 비교적 쉽게 생각할 수 있었다. 하지만, 막상 이 아이디어를 코드로 구현하려고 하니 쉽게 작성할 수 없었다. 특히, 블록을 회전하는 과정에서 막혔는데 해설에 나와있는 방법은 전혀 떠올리지 못 했다. 개인적으로 블록이 회전할 때 나타나는 패턴에 대해 고민했지만 이를 코드로 구현하려고 했지만 결과적으로 옳은 방법은 아니었다. 재귀 호출을 통한 방법은 아직 몇 문제 풀어보지는 않았지만 쉽게 감이 오지 않는 것이 아쉽게 느껴진다.

---

github : Algorithmic_Problem_Soving_Strategies/q2_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies