99클럽 코테 스터디 11일차 TIL + 퍼즐 조각 채우기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/84021

각종 빈출되는 배열 회전

링크

문제 풀이 참고

from collections import deque

dr= [-1,1,0,0]
dc=[0,0,-1,1]

## 보드 : 채워져야 하는 칸 : 0
## 퍼즐 : 채워짐에 이용되는 퍼즐이 있는 칸 : 1
def find(board, t):
    R, C = len(board), len(board[0])
    visited = [[False for _ in range(C)] for _ in range(R)]
    blocks = []
    
    for i in range(R):
        for j in range(C):
            if (board[i][j])!=t or (visited[i][j]):
                continue

            block = []
            que = deque()
            que.append([i,j])
            visited[i][j]=True
            while que:
                r,c = que.popleft()
                block.append([r,c])
                for idx in range(4):
                    nr, nc = r+dr[idx], c+dc[idx]
                    if not(0<=nr<R) or not(0<=nc<C) or visited[nr][nc] or board[nr][nc]!=t:
                        continue
                    que.append([nr, nc])
                    visited[nr][nc]=True
            blocks.append(block)
    blocks.sort()
    return blocks

            
                
## 2차원 테이블로 보정
def tableMatrix(blocks):
    minR, minC = float("inf"), float("inf")
    maxR, maxC  = -float("inf"), -float("inf")
    for r, c in blocks:
        maxR, maxC = max(maxR, r), max(maxC,c)
        minR, minC = min(minR, r), min(minC,c)
    ##print(maxR, minR, maxC, minC)
    
    R = maxR-minR+1
    C = maxC-minC+1
    matrix = [[0 for _ in range(C)] for _ in range(R)]
    newBlocks = []
    for r,c in blocks:
        matrix[r-minR][c-minC]=1
    return matrix
        
def rotate90(board):
    R, C = len(board), len(board[0])
    matrix = [[0 for _ in range(R)] for _ in range(C)]
    for r in range(R):
        for c in range(C):
            matrix[c][R-r-1]=board[r][c]
    return matrix
    

def solution(game_board, puzzle_board):
    answer = 0
    gameBlocks = find(game_board, 0)
    puzzleBlocks = find(puzzle_board, 1)
    for gameBlock in gameBlocks:
        
        gb = (tableMatrix(gameBlock))
        filled = False
        for puzzleBlock in puzzleBlocks:
            pb = tableMatrix(puzzleBlock)
            if filled:
                break
            for _ in range(4):
                rotated = rotate90(pb)
                if rotated ==gb:
                    answer+=(len(gameBlock))
                    puzzleBlocks.remove(puzzleBlock)
                    filled=True
                    break
                pb = rotated


    return answer