[Leetcode/파이썬] 427. Construct Quad Tree

Construct Quad Tree

---

Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.

Return the root of the Quad-Tree representing grid.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

• val: True if the node represents a grid of 1's or False if the node represents a grid of 0's. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.
• isLeaf: True if the node is a leaf node on the tree or False if the node has four children.

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

We can construct a Quad-Tree from a two-dimensional area using the following steps:

1. If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
2. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
3. Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

You don't need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

 

Example 1:

Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represents False and 1 represents True in the photo representing the Quad-Tree.

Example 2:

Input: grid = 
[[1,1,1,1,0,0,0,0],
[1,1,1,1,0,0,0,0],
[1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1],
[1,1,1,1,0,0,0,0],
[1,1,1,1,0,0,0,0],
[1,1,1,1,0,0,0,0],
[1,1,1,1,0,0,0,0]]

Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:

 

Constraints:

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

 

첫 번째 시도

from typing import *


# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight


class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        # isLeaf 는 말단이냐? 맞으면 1 아니면 0
        # 말단이 아니면 그냥 val은 1로 두는게 맞을듯? 1이랑 0이랑 섞여있으니까
        # 그럼 n을 계속 나눠가야겠네
        n = len(grid)
        res = self.checkLeaf(grid)

        return res
    def checkLeaf(self, grid : List[List[int]]) :
        n = len(grid)
        sm = 0

        for i in range(n) :
            for j in range(n) :
                sm += grid[i][j]

        if sm == n*n :
            return self.add_tree1(grid, Node(0, 0, None, None, None, None))
        elif sm == 0 :
            return self.add_tree2(grid, Node(0, 0, None, None, None, None))
        else :
            return self.add_tree3(grid, Node(0, 0, None, None, None, None))

    def add_tree1(self, grid: List[List[int]], node: "Node") :
        node.val = True
        node.isLeaf = True
        
        return node

    def add_tree2(self, grid: List[List[int]], node: "Node") :
        node.val = 0
        node.isLeaf = 1
    
        return node

    def add_tree3(self, grid: List[List[int]], node: "Node") :
        n = len(grid)
        node.val = 1
        node.isLeaf = 0
        node.topLeft = self.checkLeaf(grid[:n//2][:n//2])
        node.topRight = self.checkLeaf(grid[n//2 + 1:][:n//2])
        node.bottomLeft = self.checkLeaf(grid[:n//2][n//2+1:])
        node.bottomRight = self.checkLeaf(grid[n//2+1:][n//2+1:])

        return node

두 번째 시도

"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        # Node : val, isLeaf, topLeft, topRight, bottomLeft, bottomRight
        node = Node(False, True, None, None, None, None)
        n = len(grid)
        if n == 1 :
            node.val = True if grid[0][0] == 1 else False
            return node

        return self.my_construct(grid, 0, 0, n)

    def my_construct(self, grid : List[List[int]], sr, sc, delta) :
        one, zero = False, False

        for row in grid[sr:sr+delta] :
            col = row[sc:sc+delta] 
            for local_v in col :
                if local_v == 0 :
                    zero |= True
                else :
                    one |= True

        # 0 으로만 구성됨
        if one == False and zero == True :
            return Node(False, True, None, None, None, None)
        
        # 1 로만 구성됨
        if one == True and zero == False :
            return Node(True, True, None, None, None, None)

        return Node(True, False, 
                    self.my_construct(grid, sr, sc, delta//2),
                    self.my_construct(grid, sr, sc + delta//2, delta//2),
                    self.my_construct(grid, sr+delta//2, sc, delta//2),
                    self.my_construct(grid, sr+delta//2, sc+delta//2, delta//2),)

세 번째 시도

"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        # Node : val, isLeaf, topLeft, topRight, bottomLeft, bottomRight
        node = Node(False, True, None, None, None, None)
        n = len(grid)
        if n == 1 :
            node.val = True if grid[0][0] == 1 else False
            return node
        
        return self.checkLeaf(grid, 0, 0, n)

    def checkLeaf(self, grid : List[List[int]], sr: int, sc: int, leng: int) :
        sm = 0

        for row in grid[sr:sr+leng] : 
            col = row[sc:sc+leng]
            for v in col :
                sm += v

        # 1로만 구성됨
        if sm == leng * leng:
            return Node(True, True, None, None, None, None)
        # 0으로만 구성됨
        elif sm == 0 :
            return Node(False, True, None, None, None, None)
        else :
            return Node(True, False, 
                        self.checkLeaf(grid, sr, sc, leng//2),
                        self.checkLeaf(grid, sr, sc+leng//2, leng//2),
                        self.checkLeaf(grid, sr+leng//2, sc, leng//2),
                        self.checkLeaf(grid, sr+leng//2, sc+leng//2,leng//2),)

나중에 코데풀님이 설명해주시겠지... 

첫 번째 시도는 순수 내 머리로 만든 코드 : 아 슬라이싱을 이용해서 풀어야 겠다. 근데 프린트 해보니까 슬라이싱이 전혀 되지 않음, 행으로는 잘리는데 열로 안 잘림. 

두 번째 시도 : 코데풀님 코드 참고 => 슬라이싱 방법 체득

세 번째 시도 : 내 코드 + 코데풀님 슬라이싱 방법 채용 : 잘 풀렸음...

더 디테일한 부분에서 수정이 필요하겠지만, 이따 스터디때 자세하게 물어보자.