프로그래머스) 퍼즐 조각 채우기 (lv.3)

 

https://school.programmers.co.kr/learn/courses/30/lessons/84021?language=python3

프로그래머스

 

탐색을 통해서 도형의 모양을 찾고 보드에 넣을 수 있는 도형의 크기의 합을 구하는 문제이다. 

 

먼저, 보드를 돌면서 맞춰야 하는 퍼즐의 모양을 dfs를 통해 탐색하였다. 여기서 position은 가장 기준의 되는 부분을 (0, 0)으로 잡고 상하좌우 네 방향으로 돌면서 기준점에서 이동하는 방향을 통해 block을 구한다. 

 

보드 안에있는 모든 구멍을 다 구해서 blocks 배열에 넣었으면 이제 테이블을 돌면서 퍼즐 모양을 같은 dfs 방식을 통해서 구한다. 만약 퍼즐이 blocks 배열 안에 있어 보드의 구멍에 맞는다면 도형이 사용되었음(방문표시)을 뜻하는 2를 이용해 퍼즐보드를 채워주고 아니라면 퍼즐보드를 90도 방향으로 회전시켜 다시 퍼즐 모양을 찾아 보드에 맞는 퍼즐을 찾는다. 

 

import copy
def solution(game_board, table):
    def dfs(graph, x, y, position, n, num) :
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        result = [position]
        for i, j in directions:
            nx, ny = x+i, y+j
            if 0<= nx <n and 0<=ny<n and graph[nx][ny] == num : 
                graph[nx][ny] = 2
                result += dfs(graph, nx, ny, [position[0]+i, position[1]+j], n, num)
        return result 
    
    def rotate(graph) :
        n = len(graph)
        result = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(n) :
                result[j][n-1-i] = graph[i][j]
        return result            
            
    answer = 0
    game_board_copy = copy.deepcopy(game_board)
    n = len(game_board)
    blocks = []
    
    for i in range(n) :
        for j in range(n) :
            if game_board_copy[i][j] == 0 :
                game_board_copy[i][j] = 2
                blocks.append(dfs(game_board_copy, i, j, [0,0], n, 0))
                
    for _ 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
                    block = dfs(table_rotate_copy, i, j, [0, 0], n, 1)
                    if block in blocks:
                        blocks.pop(blocks.index(block))
                        answer += len(block)
                        table = copy.deepcopy(table_rotate_copy)
                    else : 
                        table_rotate_copy = copy.deepcopy(table)
    return answer

 

 

 

 

(참고한 사이트)

https://bladejun.tistory.com/164

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