[프로그래머스] 퍼즐 조각

문제 이해하기

아래의 그림과 같이 게임 보드와 테이블이 주어지는데 테이블의 블럭들을 사용해서 게임보드에 최대한 채워넣어주면 된다.

단 테이블에 있는 블록을 게임보드에 채워 넣을 땐 주위에 빈 칸이 있으면 안된다는 몇 가지의 조건을이 존재합니다.

문제 해결 방법 설명하기

1. 테이블에서 블럭의 모양을 추출한 후 roate 배열을 저장

블럭들의 회전 배열을 만들기 위해선 블럭의 모양을 알아야 합니다. 이를 위해서 저는 BFS를 사용해 블럭들을 상대좌표로 변환했습니다. 코드를 보면 연결된 블록을 찾기 위해서 절대좌표를 사용해 BFS탐색을 진행합니다. 만약 인접한 블록이 발견됐다면 해당 좌표를 상대 좌표로 변환해줍니다.

def bfs(x, y, board, visited, choice = 0):
    queue = deque()
    relative_tables = []
    queue.append([x, y, 0, 0])
    
    while queue:
        absolute_x, absolute_y, relative_x, relative_y = queue.popleft()
        
        visited[absolute_x][absolute_y] = True
        relative_tables.append([relative_x, relative_y])
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = absolute_x + dx, absolute_y + dy
            
            if nx < 0 or nx >= len(board) or ny < 0 or ny >= len(board):
                continue
            
            if visited[nx][ny]:
                continue
            
            if board[nx][ny] == choice:
                continue
            
            visited[nx][ny] = True
            queue.append([nx, ny, relative_x + dx, relative_y + dy])
    
    return relative_tables

 

2. 블럭의 상대좌표들을 모두 회전하여 저장합니다.

table 배열에서 추출된 모든 블록은 회전되어야 합니다. 저는 딕셔너리를 활용하여 회전된 블록을 관리했습니다. 그 이유는 회전된 블록을 사용해서 게임 보드를 채우게 되면 해당 블록 및 해당 블록에서 회전된 블록들을 앞으로는 사용하지 못하게 됩니다. 이를 고려하여 리스트에서 해당 블록들을 삭제하는 작업은 번거로울 수 있습니다. 반면에 딕셔너리를 이용하면 키만 제거하면 되기 때문에 삭제 작업이 간편합니다.

    rotated_table = {}    
    
    for idx in range(len(tables)):
        left = []
        right = []
        cross = []
        org = []
        
        for arr in tables[idx]:
            org.append(arr)
            left.append([-arr[1], arr[0]])
            right.append([-arr[0], -arr[1]])
            cross.append([arr[1], -arr[0]])
        
        
        rotated_table[idx] = []
        
        rotated_table[idx].append(org)
        rotated_table[idx].append(org)
        rotated_table[idx].append(left)
        rotated_table[idx].append(right)
        rotated_table[idx].append(cross)

 

3. 회전 블럭들을 게임보드에 대입하면 됩니다.

1. 게임보드에서 빈칸을 발견했다면 연결된 빈칸을 모두 추출함
2. 빈칸 크기와 회전 배열의 크기를 비교해서 연산 횟수를 줄임
3. 회전 배열들을 대입해서 해당 빈칸에 모두 들어가는지 확인합니다.
4. 모두 들어간다면 해당 블럭으로 게임 보드를 채우고, 해당 블럭은 회전 블록 배열에서 제거함 

def checkboard(boards, start_x , start_y, rotates):
    candinate_rotate_idx = []
    temp_rotate = []
    
    visited_table = [[False] * len(boards) for _ in range(len(boards))]
    coords = bfs(start_x, start_y, boards, visited_table, 1)
    
    for i in rotates:
        for rotate in rotates[i]:
            if len(rotate) != len(coords):
                continue
             
            is_successed = True
            
            for coord in rotate:
                mx = start_x + coord[0]
                my = start_y + coord[1]
                
                
                if out_of_range(mx, my, len(boards)):
                    is_successed = False
                    break
                
                if boards[mx][my]:
                    is_successed = False
                    break
            
            if is_successed:
                candinate_rotate_idx.append(i)
                temp_rotate.append(rotate)
                break
            
        if candinate_rotate_idx:
            break
        
    
    for rotate in temp_rotate:
        for coord in rotate:
            mx = start_x + coord[0]
            my = start_y + coord[1]
                
            boards[mx][my] = 1
            
    if candinate_rotate_idx:
        return candinate_rotate_idx[0]

    return -1    
    
    
 ## 여기서부턴 메인함수
    for x in range(len(game_board)):
        for y in range(len(game_board[x])):
            if game_board[x][y] == 0:
                is_deleted = checkboard(game_board, x, y, rotated_table)
                if is_deleted != -1:
                    answer += len(rotated_table[is_deleted][0])
                    # print(answer)
                    del rotated_table[is_deleted]

 

코드

from collections import deque

def out_of_range(x, y, n):
    return x < 0 or x >= n or y < 0 or y >= n

def bfs(x, y, board, visited, choice = 0):
    queue = deque()
    tables = []
    queue.append([x, y, 0, 0])
    
    while queue:
        x, y, mx, my = queue.popleft()
        
        visited[x][y] = True
        tables.append([mx, my])
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            
            if nx < 0 or nx >= len(board) or ny < 0 or ny >= len(board):
                continue
            
            if visited[nx][ny]:
                continue
            
            if board[nx][ny] == choice:
                continue
            
            visited[nx][ny] = True
            queue.append([nx, ny, mx + dx, my + dy])
    
    return tables

def checkboard(boards, start_x , start_y, rotates):
    candinate_rotate_idx = []
    temp_rotate = []
    
    visited_table = [[False] * len(boards) for _ in range(len(boards))]
    coords = bfs(start_x, start_y, boards, visited_table, 1)
    
    for i in rotates:
        for rotate in rotates[i]:
            if len(rotate) != len(coords):
                continue
             
            is_successed = True
            
            for coord in rotate:
                mx = start_x + coord[0]
                my = start_y + coord[1]
                
                
                if out_of_range(mx, my, len(boards)):
                    is_successed = False
                    break
                
                if boards[mx][my]:
                    is_successed = False
                    break
            
            if is_successed:
                candinate_rotate_idx.append(i)
                temp_rotate.append(rotate)
                break
            
        if candinate_rotate_idx:
            break
        
    
    for rotate in temp_rotate:
        for coord in rotate:
            mx = start_x + coord[0]
            my = start_y + coord[1]
                
            boards[mx][my] = 1
            
    if candinate_rotate_idx:
        return candinate_rotate_idx[0]

    return -1

def solution(game_board, table):
    answer = 0
    
    tables = []
    visited_table = [[False] * len(table) for _ in range(len(table))]
    
    for i in range(len(table)):
        for j in range(len(table[i])):
            if visited_table[i][j]:
                continue
            
            if table[i][j] == 1:
                tables.append(bfs(i, j, table, visited_table))
    
    rotated_table = {}    
    
    for idx in range(len(tables)):
        left = []
        right = []
        cross = []
        org = []
        
        for arr in tables[idx]:
            org.append(arr)
            left.append([-arr[1], arr[0]])
            right.append([-arr[0], -arr[1]])
            cross.append([arr[1], -arr[0]])
        
        
        rotated_table[idx] = []
        
        rotated_table[idx].append(org)
        rotated_table[idx].append(org)
        rotated_table[idx].append(left)
        rotated_table[idx].append(right)
        rotated_table[idx].append(cross)
    
    for x in range(len(game_board)):
        for y in range(len(game_board[x])):
            if game_board[x][y] == 0:
                is_deleted = checkboard(game_board, x, y, rotated_table)
                if is_deleted != -1:
                    answer += len(rotated_table[is_deleted][0])
                    # print(answer)
                    del rotated_table[is_deleted]

    
    return answer
if __name__ == "__main__":
    game_board = [[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]]
    table = [[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]]
    
    print(solution(game_board, table))

 

배운점 정리하기

상대좌표는 블럭의 시작점에 따라서 달라질 수 있다. 따라서 모든 게임보드를 탐색해야만한다.