Leetcode 427. Construct Quad Tree with Python

문제

문제출처

n * n 2차원배열에 0이나 1이 있다.

이를 통해 쿼드-트리를 생성후 그의 루트를 리턴하세요.

노드의 형태는 다음과 같습니다.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

1. isLeaf : Terminal node인지의 여부
2. val : Node의 값, Terminal node가 아니면 아무거나 가능.

위와 같이 생긴 배열을 나눌시

위와 같이 생기는데, 모든 값이 같으면 Terminal node가 된다는 것이다.

제한

• n == grid.length == grid[i].length
• n == 2^x where 0 <= x <= 6

풀이법

Recursive하게 풀되, 값이 모두 같을경우를 항상 체크한다.

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        def connection(currentSize: int, rs: int, cs: int):
            node = Node(False, False, None, None, None, None)
            
            # 값이 모두 같은지 확인하는 부분
            initial = grid[rs][cs]
            cnt = 0
            
            for i in range(rs, rs + currentSize):
                for j in range(cs, cs + currentSize):
                    if initial == grid[i][j]: cnt += 1
                    
            half = currentSize // 2
                    
            if cnt == currentSize ** 2:
                node.val = grid[rs][cs]
                node.isLeaf = True
            elif currentSize != 1:
                node.val = True
                node.isLeaf = False
                node.topLeft = connection(half, rs, cs)
                node.topRight = connection(half, rs, cs + half)
                node.bottomLeft = connection(half, rs + half, cs)
                node.bottomRight = connection(half, rs + half, cs + half)
            else:
                node.val = grid[rs][cs]
                node.isLeaf = True
            return node
        return connection(len(grid), 0, 0)