[알고리즘][2][RE] 퍼즐 조각 채우기

이번 풀이를 통해서는 원본은 항상 복사본과 분리가 되어야 함을 배웠다

문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

조각은 한 번에 하나씩 채워 넣습니다.
조각을 회전시킬 수 있습니다.
조각을 뒤집을 수는 없습니다.
게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.

puzzle_5.png

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

puzzle_6.png

3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

puzzle_7.png

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항
3 ≤ game_board의 행 길이 ≤ 50
game_board의 각 열 길이 = game_board의 행 길이
즉, 게임 보드는 정사각 격자 모양입니다.
game_board의 모든 원소는 0 또는 1입니다.
0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
table의 행 길이 = game_board의 행 길이
table의 각 열 길이 = table의 행 길이
즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
table의 모든 원소는 0 또는 1입니다.
0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
game_board에는 반드시 하나 이상의 빈칸이 있습니다.
table에는 반드시 하나 이상의 블록이 놓여 있습니다.
입출력 예
game_board	table	result
[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]	[[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]	14
[[0,0,0],[1,1,0],[1,1,1]]	[[1,1,1],[1,0,0],[0,0,0]]	0
입출력 예 설명
입출력 예 #1

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

puzzle_9.png

입출력 예 #2

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

나의 풀이

- bfs와 rotate를 잘 쓰면 풀리는 아주 복잡한 문제

from collections import deque
from copy import deepcopy

def solution(game_board, table):
    # 최댓값을 찾아야 하므로 그리디, DP, 탐색
    # 그래프가 나온다면 탐색!
    # 그래프의 형태를 찾는 것은 bfs로도 가능하다
    # block은 딱 맞아야 한다. 그게 핵심!
    
    
    def bfs(graph, start, criteria):
        x, y = start
        if graph[y][x] != criteria:
            return 0
        
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        
        n = len(graph)
        block = []
        block.append(start)
        
        q = deque()
        q.append(start)
        graph[y][x] = abs(criteria - 1)
        
        while q:
            x, y = q.popleft()
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if not (0<=nx<n and 0<=ny<n):
                    continue
                
                if graph[ny][nx] != criteria:
                    continue
                
                q.append((nx, ny))
                graph[ny][nx] = abs(criteria - 1)
                block.append((nx, ny))
        
        origin_x, origin_y = block[0]
        ret_block = list(map(lambda x: (x[0]-origin_x, x[1]-origin_y), block))
        
        return ret_block
    
    def rotate(graph):
        n = len(graph)
        rotate_graph = deepcopy(graph)
        for i in range(n):
            for j in range(n):
                rotate_graph[i][j] = graph[j][n-i-1]
        return rotate_graph
        
    width = len(game_board)
    blocks = []
    for i in range(width):
        for j in range(width):
            ret_block = bfs(game_board, (i, j), 0)
            
            if ret_block:
                blocks.append(ret_block)
    
    
    # table 돌리기
    answer = 0
    for _ in range(4):
        copy_table = deepcopy(table)
        for i in range(width):
            for j in range(width):
                ret_block = bfs(copy_table, (i, j), 1)
                
                if ret_block in blocks:
                    blocks.remove(ret_block)
                    table = copy_table
                    answer += len(ret_block)
                else:
                    copy_table = deepcopy(table)
        
        table = rotate(table)
    
    return answer

- 맞기는 맞았지만 아주 큰 실수를 저질렀다. (수정: 이 코드로 풀게 되면 시간초과가 난다)

- 아래와 같이 if copy_table[j][i] == 1 문을 붙이게 되면 틀리게 되는데 그 이유는 table = copy_table을 할 때 table = deepcopy(copy_table)을 하지 않으면 copy_table이 변함에 따라 table도 변하게 되기 때문이다.

- 이게 위의 코드처럼 if문이 없다면 0일때 항상 copy_table = deepcopy(table)이 실행되니까 copy_tabler과 table이 분리가 돼서 문제가 발생하지 않았는데 if문을 써주게 된다면 0일때는 copy_table과 table이 분리되지 않는다. 따라서 copy_table이 변하게 되면 table도 변하게 되어 원본을 주는게 아닌 왜곡된 정보를 주게 되었던 것이다!!

answer = 0
    for _ in range(4):
        copy_table = deepcopy(table)
        for i in range(width):
            for j in range(width):
                if copy_table[j][i] == 1:
                    ret_block = bfs(copy_table, (i, j), 1)
                    
                    if ret_block in blocks:
                        blocks.remove(ret_block)
                        table = copy_table
                        answer += len(ret_block)
                    else:
                        copy_table = deepcopy(table)

        table = rotate(table)

따라서 아래의 코드와 같이 바꿔주어야 한다. 이렇게 하면 시간도 잡을 수 있고 오류도 없다.

이번 풀이를 통해서는 원본은 항상 복사본과 분리가 되어야 함을 배웠다

from collections import deque
from copy import deepcopy

def solution(game_board, table):
    # 최댓값을 찾아야 하므로 그리디, DP, 탐색
    # 그래프가 나온다면 탐색!
    # 그래프의 형태를 찾는 것은 bfs로도 가능하다
    # block은 딱 맞아야 한다. 그게 핵심!
    
    
    def bfs(graph, start, criteria):
        x, y = start
        if graph[y][x] != criteria:
            return None
        
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        
        n = len(graph)
        block = []
        block.append(start)
        
        q = deque()
        q.append(start)
        graph[y][x] = abs(criteria - 1)
        
        while q:
            x, y = q.popleft()
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if not (0<=nx<n and 0<=ny<n):
                    continue
                
                if graph[ny][nx] != criteria:
                    continue
                
                q.append((nx, ny))
                graph[ny][nx] = abs(criteria - 1)
                block.append((nx, ny))
        
        origin_x, origin_y = block[0]
        ret_block = list(map(lambda x: (x[0]-origin_x, x[1]-origin_y), block))
        
        return ret_block
    
    def rotate(graph):
        n = len(graph)
        rotate_graph = deepcopy(graph)
        for i in range(n):
            for j in range(n):
                rotate_graph[i][j] = graph[j][n-i-1]
        return rotate_graph
        
    width = len(game_board)
    blocks = []
    for i in range(width):
        for j in range(width):
            ret_block = bfs(game_board, (i, j), 0)
            
            if ret_block:
                blocks.append(ret_block)
    
    
    # table 돌리기
    answer = 0
    for _ in range(4):
        copy_table = deepcopy(table)
        for i in range(width):
            for j in range(width):
                if copy_table[j][i] == 1:
                    ret_block = bfs(copy_table, (i, j), 1)
                    
                    if ret_block in blocks:
                        blocks.remove(ret_block)
                        table = deepcopy(copy_table)
                        answer += len(ret_block)
                    else:
                        copy_table = deepcopy(table)

        table = rotate(table)
    
    return answer