테트로미노 2차원 배열로 관리하기

문제

프로그래머스

 

---

 

재정의

테트로미노가 주어지고, 보드판이 주어진다.

보드판에 최대 몇 칸을 채울 수 있는지 확인하는 문제.

회전을 해서 넣을 수 있다.

문제는 테트로미노가 고정적이 아니라, 보드로 주어진다는 점.

 

테트로미노를 획득하고, 보드판에 맞는지 확인하는 과정은 어렵지 않다.

DFS로 블럭 형태를 결정하고, 이에 맞는 보드판이 있는지 DFS 확인하고 비교하면 된다.

 

블럭을 어떻게 저장할 것이며

블럭의 회전을 어떻게 구현할 것인가가 핵심인 문제.

 

---

 

상대 좌표로 관리하기

시작 지점을 0, 0으로 계산하고 상대좌표를 계산하면 형태를 기록할 수 있다.

 

def get_blocks(board: List[List[int]], find: int) -> List[List[Tuple[int]]]:
        blocks = []
        for y in range(len(board)):
            for x in range(len(board[0])):
                if board[y][x] != find:
                    continue
                
                stack = [(x, y)]
                routes = [(0, 0)]
                board[y][x] = not find
                
                while stack:
                    _x, _y = stack.pop()
                    for dx, dy in zip(DX, DY):
                        new_x = _x+dx
                        new_y = _y+dy
                        
                        if not(0<=new_x<len(board[0]))\
                                or not(0<=new_y<len(board))\
                                or board[new_y][new_x] != find:
                            continue
                        
                        board[new_y][new_x] = not find
                        stack.append((new_x, new_y))
                        routes.append((new_x-x, new_y-y))
                
                blocks.append(routes)
        return blocks

 

route에다가 DFS를 기록한다.

기록시에 시작지점을 빼서 상대좌표로 기록한다.

 

---

 

좌표 배열화

하지만 상대좌표로만 저장을 하게 되면, 회전이 쉽지 않다.

회전을 하게 되면, 상대좌표가 깨지기 때문이다. 그래서 상대 좌표가 아닌 배열로 저장하는 것이 유리하다.

 

# 상대적 좌표로 구성된 블럭을 2*2 matrix로 변경한다.
    def pos_to_matrix(pos:List[Tuple[int]]):
        x_list = [i[0] for i in pos]
        y_list = [i[1] for i in pos]
        
        mx_x, mn_x = max(x_list), min(x_list)
        mx_y, mn_y = max(y_list), min(y_list)
        
        matrix = [[0]*(mx_x-mn_x+1)
                    for _ in range(mx_y-mn_y+1)]
        
        for x, y in pos:
            x -= mn_x
            y -= mn_y
            
            matrix[y][x] = 1
        
        return matrix

 

평행이동을 통해 최소 값을 (0, 0)으로 교정하고

이를 그대로 배열로 만들면, 상대좌표를 배열로 저장할 수 있다.

이렇게 정의하면 회전은 그냥 2차원 배열의 회전이기 때문에 어렵지 않다.

 

---

 

2차원 배열 회전

 

이는 단순하게 루프로 해결할 수 있다.

 

def spin(block: List[List[int]]) -> List[List[int]]:
        spined_block = [[0] * len(block) for _ in range(len(block[0]))]

        for i in range(len(block)):
            for idx, val in enumerate(block[i]):
                spined_block[len(block[0])-1-idx][i] = val

        return spined_block

 

그리고 최종적으로 회전을 하면서 맞는지 비교하면 끝이다.

 

g_blocks = get_blocks(game_board, 0)
    t_blocks = get_blocks(table, 1)
    ret = 0
    
    for g_block in g_blocks:
        aim_matrix = pos_to_matrix(g_block)
        flag = False
        
        for t_block in t_blocks:
            matrix = pos_to_matrix(t_block)
            
            for _ in range(4):
                matrix = spin(matrix)
                if aim_matrix == matrix:
                    ret += len(t_block)
                    t_blocks.remove(t_block)
                    flag = True
                    break
            
            if flag:
                break
                    
    return ret

 

---

 

피드백

 

호흡이 긴 문제이다.

빡구현인 만큼 실수를 안하게 변수명, 변수 관리에 유의할 것.

설계 단에서 부터 확실하게 해서, 깔끔한 구조를 가져감에 대해서 고민할 것,