퍼즐 조각 채우기 - 프로그래머스 Python

문제: 
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.조각은 한 번에 하나씩 채워 넣습니다.조각을 회전시킬 수 있습니다.조각을 뒤집을 수는 없습니다.게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한 사항:
3 ≤ game_board의 행 길이 ≤ 50game_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에는 반드시 하나 이상의 블록이 놓여 있습니다.

 

 

생각해 볼 점 
1. 격자? →  BFS/DFS 예상하자 
2. 회전 가능? →  90도씩 회전 시킬거 생각하자 
=> 결국 좌표 뽑아서 다 돌려보고 맞는 조각 선택하는 문제!

 

내 풀이: 

어떻게 풀어야 하나 감이 안 잡혀서 이건 그냥 클로드보고 했다. 대략 방식은: 

 

1. board 를 탐색하다가 빈 공간을 발견하면 BFS 로 이어져 있는 빈 공간의 좌표를 모두  empty_spaces 라는 리스트에 넣기

2.  table 을 탐색하다가 블록을 발견하면 BFS 로 이어져 있는 블록의 좌표를 모두 pieces 라는 리스트에 넣기

→  근데 이 리스트들에 넣기 전에 noramlize라는 함수를 거친다. 그래서 모양이 일치해도 위치가 달라서 다르게 판단되는 블록이 없도록

3. empty_spaces 에 있는 공간을 90도씩 돌려보면서 pieces 에 일치하는게 있는지 찾는다. 일치하면 그 조각은 사용 처리

4. 그 조각의 len 을 answer에 누적해서 더해서 답을 구한다. 

 

from collections import deque

def solution(game_board, table):
    n = len(game_board)
    
    def bfs(board, start_r, start_c, target, visited):
        q = deque([(start_r, start_c)])
        visited[start_r][start_c] = True
        cells = []
        while q:
            r, c = q.popleft()
            cells.append((r, c))
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr, nc = r+dr, c+dc
                if 0 <= nr < n and 0 <= nc < n:
                    if not visited[nr][nc] and board[nr][nc] == target:
                        visited[nr][nc] = True
                        q.append((nr, nc))
        return cells
    
    def normalize(cells):
        min_r = min(r for r, c in cells)
        min_c = min(c for r, c in cells)
        return sorted((r - min_r, c - min_c) for r, c in cells)
    
    def rotate(cells):
        return normalize([(c, -r) for r, c in cells])
    
    # game_board 빈칸(0) 덩어리 추출
    visited = [[False]*n for _ in range(n)]
    empty_spaces = []
    for r in range(n):
        for c in range(n):
            if not visited[r][c] and game_board[r][c] == 0:
                cells = bfs(game_board, r, c, 0, visited)
                empty_spaces.append(normalize(cells))
    
    # table 조각(1) 덩어리 추출
    visited = [[False]*n for _ in range(n)]
    pieces = []
    for r in range(n):
        for c in range(n):
            if not visited[r][c] and table[r][c] == 1:
                cells = bfs(table, r, c, 1, visited)
                pieces.append(normalize(cells))
    
    # 매칭
    used = [False] * len(pieces)
    answer = 0
    
    for space in empty_spaces:
        for i, piece in enumerate(pieces):
            if used[i]:
                continue
            rotated = piece
            matched = False
            for _ in range(4):
                if rotated == space:
                    used[i] = True
                    answer += len(space)
                    matched = True
                    break
                rotated = rotate(rotated)
            if matched:
                break
    
    return answer