Programmers - 퍼즐 조각 채우기

문제 링크

dfs + 시뮬레이션 문제이다.

get_blocks() : dfs를 이용해서 모든 block을 구하고 2차원 배열로 만든다
match() : 현재 board에 block을 끼울 수 있는지 확인 후 끼울 수 있으면 끼운다

match() 내부 함수 설명
 1. rotate90(): 블록을 90도 회전
 2. has_space(): 블록이 들어갈 공간이 있는지 확인
 3. is_correct_match(): 알맞은 자리인지 확인.(인접한 칸이 비어있으면 안됨)
 4. insert(): 블록 삽입
 5. rollback(): 블록 제거 
   (is_correct_match를 블록 삽입 이후에만 확인할 수 있는데, 알맞는 자리가 아닐 경우 다시 되돌리기 위해 필요)

def solution(game_board, table):

    blocks = get_blocks(table)

    for block in blocks:
        match(game_board, block)

    answer = 0
    for row in game_board:
        for item in row:
            if item == 2:
                answer += 1

    return answer


def get_blocks(table):
    n = len(table)
    visit = [[False for _ in range(n)] for __ in range(n)]
    moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    blocks = []
    block = []

    def can_move(x, y):
        if not (0 <= x < n and 0 <= y < n):
            return False
        if visit[x][y]:
            return False
        return table[x][y] == 1

    def dfs(x, y):
        visit[x][y] = True
        block.append((x, y))
        for (dx, dy) in moves:
            ax = x+dx
            ay = y+dy
            if can_move(ax, ay):
                dfs(ax, ay)

    def to_array(block):
        li = []
        dx = block[0][0]
        dy = min(list(map(lambda xy: xy[1], block)))
        for (x, y) in block:
            li.append((x-dx, y-dy))

        xlist = list(map(lambda xy: xy[0], li))
        ylist = list(map(lambda xy: xy[1], li))

        height = max(xlist)+1
        width = max(ylist)-min(ylist)+1

        new_block = [[0 for _ in range(width)] for __ in range(height)]

        for (x, y) in li:
            new_block[x][y] = 2

        return new_block

    for i in range(n):
        for j in range(n):
            if can_move(i, j):
                block = []
                dfs(i, j)
                blocks.append(to_array(block))

    return blocks


def match(board, block):
    n = len(board)
    moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]

    def rotate90(block):
        return list(zip(*block[::-1]))

    def has_space(x, y):
        for i in range(len(block)):
            for j in range(len(block[0])):
                ax = x+i
                ay = y+j
                if board[ax][ay] >= 1 and block[i][j] == 2:
                    return False
        return True

    def is_correct_match(x, y):
        for i in range(len(block)):
            for j in range(len(block[0])):
                ax = x+i
                ay = y+j
                if block[i][j] != 2:
                    continue
                for move in moves:
                    mx = ax + move[0]
                    my = ay + move[1]
                    if not (0 <= mx < n and 0 <= my < n):
                        continue
                    if board[mx][my] == 0:
                        return False
        return True

    def insert(x, y):
        for i in range(len(block)):
            for j in range(len(block[0])):
                ax = x+i
                ay = y+j
                board[ax][ay] += block[i][j]

    def rollback(x, y):
        for i in range(len(block)):
            for j in range(len(block[0])):
                ax = x+i
                ay = y+j
                board[ax][ay] -= block[i][j]

    for rotate_count in range(4):
        block = rotate90(block)
        for i in range(n-len(block)+1):
            for j in range(n-len(block[0])+1):
                if has_space(i, j):
                    insert(i, j)
                    if not is_correct_match(i, j):
                        rollback(i, j)
                        continue
                    return