p_퍼즐조각채우기_84021

문제

조각은 회전가능 뒤집기 불가

답

기존에는 스탭에 따라 노드를 기억하거나 스탭(깊이)에 따른 이전스탭에 대한 차이값을 저장해야한다고생각했다, (이렇게하면 3차원이상...)

근데 걍 기준점에 대해서 갈 수 있는 노드의 리스트를 얻으면 된다. 2차원배열. (x,y저장할때 1차원생기니깐)

그리고 여기서는 조건이 있었다.

from collections import deque
import copy
move = [[-1,0],[1,0],[0,-1],[0,1]]
                       
def bfs(arr,y,x,visit):
    #  dif는 비교대상 visit table은0 다른건1
    narr = copy.deepcopy(arr)
    limit = [len(narr)-1,len(narr[0])-1]
    q = deque([(y,x)])
    shape = [(0,0)] # 기준점중심으로 바뀐 정도만 저장
    narr[y][x] = visit
    while q:
        ny,nx = q.popleft()
        for m in move:
            my = ny + m[0]
            mx = nx + m[1]
            if my<0 or mx<0 or my> limit[0] or mx > limit[1]:
                continue
            if narr[my][mx] != visit:
                continue
            narr[my][mx] = visit
            shape.append((my-y,mx-x))
            q.append((my,mx))
    return shape

def find_board(game_board,shapes):
    cnt = 0
    for i in range(len(game_board)):
        for j in range(len(game_board[0])):
            if game_board[i][j] == 0:
                shape = bfs(game_board,i,j,1)
                if shape in shapes:
                    shapes.remove(shape)
                    cnt += 1
    return [game_board,cnt]

def solution(game_board, table):
    shapes = []
    for i in range(len(table)):
        for j in range(len(table[0])):
            if table[i][j] == 1:
                shape = bfs(table,i,j,0)
                shapes.append(shape)
    
    cnt = 0
    for _ in range(4):
        [game_board,n_cnt] = find_board(game_board,shapes)
        cnt += n_cnt
        print(shapes)
        game_board = list(map(list,zip(*game_board[::-1])))
        [game_board,n_cnt] = find_board(game_board,shapes)
        cnt += n_cnt

    return cnt