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

링크

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

풀이

from collections import deque, defaultdict

def solution(game_board, table):
    return gaming(game_board, getBlocks(table))

# 테이블의 블록들을 모두 구한다.
# 블록을 구하는 시작점은 항상 0, 0 기준으로 구해주면 향후 게임보드에 적용하기가 편하다.
def getBlocks(table):
    N = len(table)
    traced = [[0]*N for _ in range(N)]
    blocks = defaultdict(int)
    
    def getBlock(r, c):
        block, q = [], deque()
        block.extend((0,0))
        traced[r][c] = 1
        q.append((r, c))
        
        while q:
            cr, cc = q.popleft()
            for nr, nc in ((cr+1,cc), (cr-1,cc), (cr,cc+1), (cr,cc-1)):
                if nr==-1 or nc==-1 or nr==N or nc==N:
                    continue    
                if table[nr][nc]==0 or traced[nr][nc]:
                    continue
                q.append((nr, nc))
                traced[nr][nc] = 1
                block.extend((nr-r, nc-c))

        return tuple(block)

    for r in range(N):
        for c in range(N):
            if table[r][c]==0 or traced[r][c]:
                continue
            # 같은 종류의 블럭이 여러개있을수 있으므로
            # defaultdict나 counter를 쓴다.
            blocks[getBlock(r, c)] += 1
    return blocks

def gaming(game_board, blocks):
    N = len(game_board)
    answer = 0
    
    def getBlock(r, c):
        block, q = [], deque()
        block.extend((0,0))
        q.append((r, c))
        game_board[r][c] = 1
        
        while q:
            cr, cc = q.popleft()
            for nr, nc in ((cr+1,cc), (cr-1,cc), (cr,cc+1), (cr,cc-1)):
                if nr==-1 or nc==-1 or nr==N or nc==N:
                    continue    
                if game_board[nr][nc]==1:
                    continue
                q.append((nr, nc))
                game_board[nr][nc] = 1
                block.extend((nr-r, nc-c))

        return tuple(block)

    # gameboard를 계속 회전해가면서
    # 블록들을 맞춰본다.
    for _ in range(4):
        for r in range(N):
            for c in range(N):
                if game_board[r][c]==1:
                    continue
                block = getBlock(r, c)

                if block in blocks:
                    blocks[block] -= 1
                    answer += (len(block)//2)
                    
                    if not blocks[block]:
                        del blocks[block]
                else:
                    for i in range(0, len(block), 2):
                        game_board[r+block[i]][c+block[i+1]] = 0
        # rotate
        game_board = zip(*[reversed(row) for row in game_board])
        game_board = [list(row) for row in game_board]

    return answer

## 이방법은 위방법과 정반대로 한다.
## gameboard에 블록이 들어갈수 있는 빈공간을 모두구한다.
## 그 빈공간을 table을 회전시키면서 맞춰보는것이다!
# def solution(game_board, table):
#     N = len(game_board)
#     blocks = defaultdict(int)
    
#     #블록 찾기 및 테이블 변환
#     for i in range(N):
#         for j in range(N):
#             table[i][j] = (table[i][j] + 1) % 2
#             if game_board[i][j] == 0:
#                 block = bfs(game_board, i, j, N)
#                 blocks[block] += 1
#     return block_matching(blocks, table, N)

# def bfs(traced, x, y, N):
#     ret = [(0, 0)]
#     q = deque()
#     traced[x][y] = -1
#     q.append((x, y, 0, 0))
    
#     while q:
#         x, y, pre_x, pre_y = q.popleft()
#         cases = ((x+1, y, pre_x+1, pre_y), (x-1, y, pre_x-1, pre_y), 
#                  (x, y+1, pre_x, pre_y+1), (x, y-1, pre_x, pre_y-1))
#         for (nx, ny, n_pre_x, n_pre_y) in cases:
#             if 0 <= nx < N and 0 <= ny < N and traced[nx][ny] == 0:
#                 traced[nx][ny] = -1
#                 q.append((nx, ny, n_pre_x, n_pre_y))
#                 ret.append((n_pre_x, n_pre_y))
#     return tuple(ret)

# def block_matching(blocks, table, N):
#     answer = 0
#     # 4방향으로 회전시켜 blanks 맞추기
#     for _ in range(4):
#         # 테이블을 회전한다.
#         table = [list(row)[::-1] for row in zip(*table)]
        
#         # traced checking을 위한 그래프 복제
#         traced = [row[:] for row in table]

#         for i in range(N):
#             for j in range(N):
#                 if traced[i][j] == 0:
#                     traced[i][j] = -1
#                     block = bfs(traced, i, j, N)
#                     if block in blocks:
#                         answer += len(block)
#                         blocks[block] -= 1
#                         if not blocks[block]: del blocks[block]
#                         # 블록 삭제 작업, 같은 블록을 trace하지 않게 삭제한다
#                         table = [row[:] for row in traced]
#                     else:
#                         traced = [row[:] for row in table]
#     return answer