[Python Algorithm] 알고스팟 게임판 덮기 - BOARDCOVER

---

풀이 과정

게임판의 빈칸 중 왼쪽 위 부분부터 탐색해서 그 부분을 채우고, 그 다음 게임판의 빈칸을 찾아서 채워가는 방식으로 구현을 하였습니다.

이때 중요한것은 중복을 없애는 것인데 게임판의 빈칸중 왼쪽 위 부분부터 아래방향으로 계속해서 채워나갈것이기 때문에 검색한 부분의 왼쪽과 위쪽에 있는 칸은 항상 채워져 있다고 가정을 해도 무방합니다.

이렇게 가정하는 경우 나올수 있는 블록의 경우의 수는 아래와 같이 4개 이므로 이렇게 해서 중복을 없애줄수 있습니다.

이후에는 백트래킹을 이용하여 게임판을 덮을수 있도록 구현하였습니다.

---

최종 코드

C = int(input())

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

def boardCover():
  x, y = -1, -1
  for i in range(H):
    for j in range(W):
      if (board[i][j] == '.'):
        x = j
        y = i
        break
    if y != -1:
      break

  if x == -1 and y == -1: return 1

  count = 0

  for cover in coverType:
    flag = True
    for dx, dy in cover:
      nx, ny = x + dx, y + dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H:
        flag = False
        break
      elif board[ny][nx] == '#':
        flag = False
        break
    if flag:
      for dx, dy in cover:
        nx, ny = x + dx, y + dy
        board[ny][nx] = '#'
      count += boardCover()
      for dx, dy in cover:
        nx, ny = x + dx, y + dy
        board[ny][nx] = '.'
  return count

for _ in range(C):
  H, W = map(int, input().split())
  board = [list(input()) for _ in range(H)]
  print(boardCover())

---

결과

---

Link

게임판 덮기 문제 출처

GitHub 코드