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

😉 아이디어

1. _!BFS!_ 활용 매트릭스별 조각 탐색

2. _!game_board!_ 조각 기준 _!table!_ 조각 대입 및 검증

3. 검증된 조각의 경우 제거 👉 데이터 중복 방지

😉 풀이

from collections import deque

def solution(game_board, table):
    answer = 0
    # 매트릭스 내 조각 탐색
    board_pieces = find_pieces(game_board, 0)
    table_pieces = find_pieces(table, 1)
            
    for blank in reversed(board_pieces):
        for puzzle in reversed(table_pieces):
            is_equal_matrix = False
            
            rotated_puzzle = puzzle
            
            # game_board 기준, table서 추출된 조각 회전 및 일치여부 검증
            for _ in range(4):
                if blank == rotated_puzzle:
                    is_equal_matrix = True
                    break
                rotated_puzzle = rotate_matrix(rotated_puzzle)
                
            if is_equal_matrix: # 조각 일치 시 각 리스트서 조각 제거
                answer += count_matrix_point(puzzle)
                table_pieces.remove(puzzle)
                board_pieces.remove(blank)
                break
                
    return answer
                
def count_matrix_point(matrix):
    count = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 1:
                count += 1
                
    return count
            
def rotate_matrix(matrix):
    num_rows = len(matrix)
    num_cols = len(matrix[0]) if num_rows > 0 else 0

    new_matrix = [[0] * num_rows for _ in range(num_cols)]

    for i in range(num_rows):
        for j in range(num_cols):
            new_matrix[j][num_rows - 1 - i] = matrix[i][j]
            
    return new_matrix

def compare_matrix(matrix1, matrix2):
    if (len(matrix1) != len(matrix2)
        or len(matrix1[0]) != len(matrix2[0])):
        return False
    
    N = len(matrix1)
    
    for i in range(N):
        for j in range(N):
            if matrix1[i][j] != matrix2[i][j]:
                return False
    
    return True

def normalize_coords(coords):
    min_x = min(x for x, y in coords)
    min_y = min(y for x, y in coords)
    return [(y - min_y, x - min_x) for x, y in coords]

def create_matrix(nomalized_coords):
    max_x = max(x for x, y in nomalized_coords)
    max_y = max(y for x, y in nomalized_coords)
    
    matrix = [[0] * (max_x + 1) for _ in range(max_y + 1)]
    
    for coords in nomalized_coords:
        matrix[coords[1]][coords[0]] = 1

    return matrix
    
def find_pieces(matrix, target_value):
    rows = len(matrix)
    cols = len(matrix[0])
    visited = [[False] * cols for _ in range(rows)]
    collected_pieces = []
    
    for row in range(rows):
        for col in range(cols):
            if matrix[row][col] == target_value and not visited[row][col]:
                collected_pieces.append(create_matrix(normalize_coords(bfs(matrix, row, col, visited, target_value))))
    
    return collected_pieces
                
def bfs(matrix, start_row, start_col, visited, target_value):
    rows = len(matrix)
    cols = len(matrix[0])
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dq = deque([(start_row, start_col)])
    visited[start_row][start_col] = True
    pieces = []
    
    while dq:
        row, col = dq.popleft()
        pieces.append((row, col))
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if (0 <= new_row < rows 
                and 0 <= new_col < cols
                and matrix[new_row][new_col] == target_value
                and not visited[new_row][new_col]):
                    visited[new_row][new_col] = True
                    dq.append((new_row, new_col))
    return pieces

✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/84021