[ALGOSPOT] 알고스팟 BOARDCOVER 게임판 덮기(Python)

www.algospot.com

[ALGOSPOT] 알고스팟 BOARDCOVER 게임판 덮기

(Python)

(글쓴날 : 2020.05.21)

 

---

* ALGOSPOT, 알고스팟 아이디 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 BOARDCOVER 게임판 덮기

---

1) 문제

문제 링크 : https://www.algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

---

2) 풀이 과정

* 시간 복잡도 : O(nm)

 

검은 칸과 흰 칸으로 구성된 H * W 크기의 게임판이 주어질 때, 3칸짜리 L자 모양을 한 블록을 자유롭게 회전시켜 모든 흰 칸을 덮을 수 있는 경우의 수를 구하는 문제입니다.

 

저의 경우, DFS를 적용하였고 Python을 사용했습니다.

먼저, L자 모양 블록의 형태를 x, y 인덱스로 표현한 2차원 방향 벡터 dx, dy를 만들어 놓은 뒤,

게임판을 깊이 우선 탐색하여, 흰 칸이 탐색 될 경우 놓을 수 있는 블록이 있는지 확인한 후 놓을 수 있다면 블록을 놓았습니다.

그렇게 블록을 채워나가다 만약, 게임판의 모든 흰 칸이 덮였을 경우 답을 1씩 증가시켜 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def DFS():
    global ans
    i, j, = -1, -1
    isFinish = True
 
    for x in range(H):
        for y in range(W):
            if not visit[x][y]:
                isFinish = False
                i, j = x, y
                break
        if not isFinish:
            break
    
    if isFinish:
        ans += 1
        return
 
    if not visit[i][j]:
        for rotate in range(4):
            isPossible = True
            possibleDirection = []
 
            for way in range(3):
                ii = i + dx[rotate][way]
                jj = j + dy[rotate][way]
 
                if ii < 0 or ii > H - 1 or jj < 0 or jj > W - 1:
                    isPossible = False
                    break
 
                if visit[ii][jj]:
                    isPossible = False
                    break
 
                possibleDirection.append((ii, jj))
 
            if isPossible:
                for pDX, pDY in possibleDirection:
                    visit[pDX][pDY] = True
 
                DFS()
                
                for pDX, pDY in possibleDirection:
                    visit[pDX][pDY] = False
                        
 
C = int(input())
dx = [[0, 1, 1], [0, 1, 0], [0, 1, 1], [0, 0, 1]]
dy = [[0, 0, -1], [0, 0, 1], [0, 0, 1], [0, 1, 1]]
 
for _ in range(C):
    ans = 0
    H, W = map(int, input().split())
    gameBoard = [list(input().rstrip()) for _ in range(H)]
 
    visit = [[False] * W for _ in range(H)]
    whiteSection = 0
    
    for i in range(H):
        for j in range(W):
            if gameBoard[i][j] == "#":
                visit[i][j] = True
            else:
                whiteSection += 1
 
    if whiteSection % 3:
        print(0)
        continue
 
    DFS()
 
    print(ans)

---