게임판 덮기

GitHub - Seungkyu-Han/PS_strategy: 알고리즘 분류하는 워크플레이스

 

algospot.com :: BOARDCOVER

게임판 덮기 문제이다.

알고스팟에 제출을 해봤는데 nonzero return code...?? 라는 에러가 뜬다.

어차피 제출할 용도가 아닌 공부용이었으니 풀어보기만 하고 제출은 하지 않도록 하겠다.

 

좌표를 모두 돌며 확인하는 브루트포스 + 해당 경우에서 더 이상 답을 찾지 못하면 돌아오는 백트래킹 방법이다.

이 문제를 풀고 생각난 건데 브루트포스는 완전탐색이다. 따라서 확인 할 수 있는 모든 경우를 찾아야 한다.

이 문제에서도 놓을 수 있는 블록의 타입을 모두 찾아야 정답이 나온다.

만약 경우를 모두 찾지 못하면 정답보다 작은 값이, 경우를 중복으로 찾았다면 정답보다 큰 값이 나오게 될 것이다.

 

이 문제에서 좌표를 x, y라고 했을 때, 놓을 수 있는 블록의 종류이다.

block = [[[0, 0], [1, 0], [0, 1]], [[0, 0], [0, 1], [1, 1]], [[0, 0], [1, 0], [1, 1]], [[0, 0], [1, 0], [1, -1]]]​

 

당연히 해당 좌표를 비우고 간다면 모든 게임판을 채울 수 없게 되고, 이 이외의 블록 종류들은 다른 칸에서 놓는 블록의 모양과 중복이 된다.

 

게임판을 받았을 때 다음으로 채워야 하는 좌표를 반환해주는 함수이다. 

def find(h_len, w_len):
    for q in range(h_len):
        for r in range(w_len):
            if board_list[q][r] == '.':
                return [q, r]
    return [-1, -1]  # 모든 칸이 덮여있으면

모든 칸에 블록이 있다면 -1, -1을 리턴해주어 호출한 곳에 알려준다.

 

게임판에 해당 타입의 종류의 블록을 놓을 수 있는지 알려주는 함수이다.

def is_blank(x, y, block_type):
    for q in range(3):
        if 0 <= x + block[block_type][q][0] < h and 0 <= y + block[block_type][q][1] < w:
            if board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] == '#':
                return False
    return True

 

게임판을 '#'으로 덮어주거나, '.'으로 치워주는 함수이다.

def cover_block(x, y, block_type, blank_or_block):
    for q in range(3):
        board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] = blank_or_block

백트래킹에서는 정답의 경우가 없으면 복구를 해줘야 하기 때문에 blank_or_block으로 '.'도 받아서 복구도 할 수 있도록 하였다.

block_type으로 블록의 종류를 받고 해당 칸 만큼 채워주거나 치워준다.

 

def solve(board_list, h, w):
    global result
    result = 0

    # 놓을 수 있는 블록의 종류
    block = [[[0, 0], [1, 0], [0, 1]], [[0, 0], [0, 1], [1, 1]], [[0, 0], [1, 0], [1, 1]], [[0, 0], [1, 0], [1, -1]]]

    def cover():
        global result

        x, y = find(h, w)
        if x == -1 and y == -1:
            result += 1
            return

        for q in range(4):
            if is_blank(x, y, q):
                cover_block(x, y, q, '#')
                cover()
                cover_block(x, y, q, '.')

    def find(h_len, w_len):
        for q in range(h_len):
            for r in range(w_len):
                if board_list[q][r] == '.':
                    return [q, r]
        return [-1, -1]  # 모든 칸이 덮여있으면

    def is_blank(x, y, block_type):
        for q in range(3):
            if 0 <= x + block[block_type][q][0] < h and 0 <= y + block[block_type][q][1] < w:
                if board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] == '#':
                    return False
        return True

    def cover_block(x, y, block_type, blank_or_block):
        for q in range(3):
            board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] = blank_or_block

    cover()
    print(result)

사용한 함수의 전체이다.

 

함수 안에 함수들을 넣어서 최대한 깔끔하게 정답을 리턴할 수 있도록 했다.

cover() 함수에서 find를 좌표들을 돌며 채워주고 복구해주는 백트래킹 방법을 사용했다.

만약 find()에서 -1, -1을 리턴받으면 외부 전역 변수 result에 +1을 해준다.

 

import sys

result = 0


def solve(board_list, h, w):
    global result
    result = 0

    # 놓을 수 있는 블록의 종류
    block = [[[0, 0], [1, 0], [0, 1]], [[0, 0], [0, 1], [1, 1]], [[0, 0], [1, 0], [1, 1]], [[0, 0], [1, 0], [1, -1]]]

    def cover():
        global result

        x, y = find(h, w)
        if x == -1 and y == -1:
            result += 1
            return

        for q in range(4):
            if is_blank(x, y, q):
                cover_block(x, y, q, '#')
                cover()
                cover_block(x, y, q, '.')

    def find(h_len, w_len):
        for q in range(h_len):
            for r in range(w_len):
                if board_list[q][r] == '.':
                    return [q, r]
        return [-1, -1]  # 모든 칸이 덮여있으면

    def is_blank(x, y, block_type):
        for q in range(3):
            if 0 <= x + block[block_type][q][0] < h and 0 <= y + block[block_type][q][1] < w:
                if board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] == '#':
                    return False
        return True

    def cover_block(x, y, block_type, blank_or_block):
        for q in range(3):
            board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] = blank_or_block

    cover()
    print(result)


for _ in range(int(sys.stdin.readline())):
    H, W = map(int, sys.stdin.readline().split())

    board = []
    blank_cnt = 0

    for i in range(H):
        board.append(list(sys.stdin.readline().strip()))
        blank_cnt += board[-1].count('.')

    # 빈칸의 수가 3의 배수가 아니면 어차피 덮지 못하니 continue
    if blank_cnt % 3 != 0:
        print(0)
        continue

    solve(board, H, W)

사용한 코드의 전체이다.

 

브루트포스에서 가장 중요한 것은 탐색할 수 있는 모든 경우의 수를 찾는 것이다.

항상 생각하고 풀 수 있도록 하자!