Programmers - 퍼즐 조각 채우기[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 퍼즐 조각 채우기

문제 설명

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

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

다음은 퍼즐 조각을 채우는 예시입니다.

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

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

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 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

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

입출력 예 #2

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

---

문제 풀이

BFS를 활용하여 다음과 같은 알고리즘으로 문제를 해결하였다.

1. BFS를 이용하여 table에서 조각의 좌표를 탐색한다.
   • 사용 함수 : bfs()
2. 받은 조각의 좌표들을 사각형 형태로 가공한다.
   • 사용 함수 : get_new_locations(), get_piece_or_space()
3. 조각과 빈 공간 간의 비교를 위해 game_board의 0과 1을 바꾼다.
4. game_board를 BFS로 탐색하며 빈 공간을 조각과 동일하게 사각형 형태로 가공하여 조각과 같은지 비교한다.
   • 사용 함수 : bfs(), get_new_locations(), get_piece_or_space()
5. 사각형 형태의 조각들을 90도 회전하며 4.을 반복한다.
   • 사용 함수 : rotate_a_matrix_by_90_degree()

 

구현 코드

코드 링크 : 퍼즐 조각 채우기

from collections import deque
import copy

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

def rotate_a_matrix_by_90_degree(a):
    row_length = len(a)
    column_length = len(a[0])
    
    res = [[0] * row_length for _ in range(column_length)]
    for r in range(row_length):
        for c in range(column_length):
            res[c][row_length-1-r] = a[r][c]
    
    return res

def get_new_locations(location):
    new_locations = []
    for loc in location:
        x_min = int(1e9)
        x_max = 0
        y_min = int(1e9)
        y_max = 0
        for x, y in loc:
            x_min = min(x_min, x)
            x_max = max(x_max, x)
            y_min = min(y_min, y)
            y_max = max(y_max, y)
        new_locations.append([x_min, x_max, y_min, y_max])
    return new_locations

def bfs(table, q, location, n):
    while q:
        x, y  = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if table[nx][ny] == 1:
                    location.append([nx, ny])
                    table[nx][ny] = 0
                    q.append([nx, ny])
    return location

def get_piece_or_space(table, new_locations):
    pieces = []
    for x_min, x_max, y_min, y_max in new_locations:
        piece = []
        for x in range(x_min, x_max+1):
            row = table[x]
            piece.append(row[y_min:y_max+1])
        pieces.append(piece)
    return pieces

def solution(game_board, table):
    answer = 0
    n = len(table)
    for x in range(n):
        for y in range(n):
            if game_board[x][y] == 0:
                game_board[x][y] = 1
            else:
                game_board[x][y] = 0

    puzzle = []
    new_table = copy.deepcopy(table)
    for x in range(n):
        for y in range(n):
            if new_table[x][y] == 1:
                new_table[x][y] = 0
                q = deque([[x, y]])
                location = [[x, y]]
                puzzle.append(bfs(new_table, q, location, n))
                
    new_locations = get_new_locations(puzzle)
    pieces = get_piece_or_space(table, new_locations)
    empty = []
    
    for _ in range(4):
        new_pieces = []
        for piece in pieces:
            new_pieces.append(rotate_a_matrix_by_90_degree(piece))
        new_game_board = copy.deepcopy(game_board)
        for x in range(n):
            for y in range(n):
                if new_game_board[x][y] == 1:
                    new_game_board[x][y] = 0
                    q = deque([[x, y]])
                    location = [[x, y]]
                    new_location = get_new_locations([bfs(new_game_board, q, location, n)])
                    space = get_piece_or_space(game_board, new_location)[0]
                    if space in new_pieces:
                        new_pieces.remove(space)
                        for x_min, x_max, y_min, y_max in new_location:
                            for x in range(x_min, x_max+1):
                                for y in range(y_min, y_max+1):
                                    if game_board[x][y] == 1:
                                        game_board[x][y] = 0
                                        answer += 1
        pieces = new_pieces

    return answer