99클럽 코테 스터디 3일차 TIL - 프로그래머스 퍼즐조각

프로그래머스 퍼즐조각

 

나의 풀이 (81% 상태)

 

1. bfs를 통해 빈칸 집합을 A에 그리고 조각들의 좌표 B에 모아본다.

2. 빈칸집합이나 조각들을 좌상단으로 정렬시켜준다.

3. 빈칸과 조각들을 매칭시켜보면서 확인한다.

4. 매칭시 조각구성 수를 세서 answer에 모두 더해준다.

 

from collections import deque
def solution(game_board, table):
    # 모양 좌표 찾기
    def bfs(board,row,col,val):
        if visited[val][row][col]:
            return
        visited[val][row][col]=True
        if board[row][col]!=val:
            return
        search=[[-1,0],[1,0],[0,1],[0,-1]]
        queue=deque()
        queue.append([row,col])
        blocks=[[row,col]]
        while queue:
            ri,ci=queue.popleft()
            for dr,dc in search:
                nr=ri+dr
                nc=ci+dc
                if 0<=nr<N and 0<=nc<N and not visited[val][nr][nc]:
                    visited[val][nr][nc]=True
                    if board[nr][nc]==val:
                        queue.append([nr,nc])
                        blocks.append([nr,nc])        
        return blocks
    # 정사각형 모양으로 스케일링
    def scaling(block_list):
        min_row=float("inf")
        min_col=float("inf")
        max_row=0
        max_col=0
        for br,bc in block_list:
            min_row=min(br,min_row)
            min_col=min(bc,min_col)
            max_row=max(br,max_row)
            max_col=max(bc,max_col)
        length=max(max_row-min_row,max_col-min_col)+1
        scaled_block=[[0 for _ in range(length)] for _ in range(length)]
        for br,bc in block_list:
            scaled_block[br-min_row][bc-min_col]=1
        return scaled_block
    
    # 회전
    def rotate(block_list):
        temp=[[0 for _ in range(len(block_list))] for _ in range(len(block_list))]
        for r in range(len(block_list)):
            for c in range(len(block_list)):
                temp[r][c]=block_list[c][len(block_list)-1-r]
        return temp
    
    A=[]
    B=[]
    N=len(game_board)
    visited=[[[False for _ in range(N)] for _ in range(N)] for _ in range(2)]
    for r in range(N):
        for c in range(N):
            x=bfs(game_board,r,c,0)
            if x:
                A.append(scaling(x))
    
    for r in range(N):
        for c in range(N):
            y=bfs(table,r,c,1)
            if y:
                B.append(scaling(y))
    
    # 3. 매칭
    answer = 0
    matched_B=[False for _ in range(len(B))]
    for a in range(len(A)):
        for b in range(len(B)):
            if not matched_B[b]:
                z=B[b] # table
                for _ in range(4):
                    z=rotate(z)
                    if A[a]==z:
                        matched_B[b]=True
                        answer+=sum(map(sum,z))
                        break    
                if matched_B[b]:
                    break
    return answer

오늘의 회고

- 내가 사용한 rotate함수는 역시계방향인것만 빼면 괜찮았다.

- 6,8.9,10 테스트 케이스가 틀렸었는데, 질문게시판을 보니 스케일링을 하면서 다른 경우가 있는지 확인해야할 것 같다.

- 조만간 다음에 다시 깔끔하게 정리하고 풀어보려고 한다.