[프로그래머스] 퍼즐조각 채우기 (파이썬)

난이도 : LV3

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/84021

문제해결

• game_board 를 순회하면서 빈공간이 있을 경우 (0,0)기준으로 빈공간 모양의 좌표를 blank 라는 리스트에 받는다.
• table 을 4방향으로 회전시키면서 테이블을 순회하고 순회하면서 발견된 각각의 도형들을 (0,0)을 기준으로 도형모양의 좌표를 받는다.
  • 만약 도형의 좌표가 blank 안에 있다면 도형의 크기 만큼 정답에 더한다. (blank 안의 도형은 삭제)

소스코드

import copy

dx,dy = [1,-1,0,0], [0,0,-1,1]

def dfs(board,x,y,position,num, n):
    result = [position]
    board[x][y] = 2
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx<n and 0<=ny<n and board[nx][ny] == num:
            board[nx][ny] = 2
            result += dfs(board,nx,ny,[position[0]+dx[i], position[1]+dy[i]],num, n)
    return result

def rotate(table):
    n = len(table)
    rotated = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            rotated[j][n-i-1] = table[i][j]
    
    return rotated
    

def solution(game_board, table):
    ans = 0
    blank = []
    n = len(game_board)
    
    for i in range(n):
        for j in range(n):
            if game_board[i][j] == 0:
                blank.append(dfs(game_board,i,j,[0,0],0,n))
    
    for k in range(4):
        table = rotate(table)
        copy_table = copy.deepcopy(table)
        for i in range(n):
            for j in range(n):
                if table[i][j] == 1:
                    shape = dfs(copy_table,i,j,[0,0],1,n)
                    if shape in blank:
                        blank.remove(shape)
                        ans += len(shape)
                        table = copy.deepcopy(copy_table)
                    else:
                        copy_table = copy.deepcopy(table)
    return ans