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

Python

방법 1

1) 도형의 형태를 추출하기 위해서 DFS 혹은 BFS를 활용

2) 추출된 도형의 형태를 기반으로 회전하는 table에서 일치하는 곳이 있는 지 확인하는 작업을 진행한다.

3) 만약 일치한다면 table을 방문했다는 update를 해야하고 일치하지 않는다면 update하지 않는다.

import copy

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

def dfs(i, j, graph, position, n, num):    
    res = [position]
    
    for k in range(4):        
        nx, ny = i + dx[k], j + dy[k]
        
        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == num:
            graph[nx][ny] = 2
            res = res + dfs(nx, ny, graph, [position[0]+dx[k], position[1]+dy[k]], n, num)
        
    return res

def rotate(lst):
    n = len(lst)
    
    o = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            o[j][n-1-i] = lst[i][j]
    return o
        
    
def solution(game_board, table):
    answer = 0
    n = len(game_board)    
    game_board_copy = copy.deepcopy(game_board)
    block = []
    
    for i in range(n):
        for j in range(n):
            if game_board_copy[i][j] == 0:
                game_board_copy[i][j] = 2
                result = dfs(i, j, game_board_copy, [0, 0], n, 0)[1:]
                block.append(result)
    
    for r in range(4):
        table = rotate(table)
        table_rotate_copy = copy.deepcopy(table)
        
        for i in range(n):
            for j in range(n):
                if table_rotate_copy[i][j] == 1:
                    table_rotate_copy[i][j] = 2
                    result = dfs(i, j, table_rotate_copy, [0, 0], n, 1)[1:]
                    if result in block:
                        
                        block.pop(block.index(result))
                        answer += (len(result)+1)                        
                        table = copy.deepcopy(table_rotate_copy)
                    else:
                        table_rotate_copy = copy.deepcopy(table)
    
    return answer

0000