2023.02.27 Today's Challenge

fabichoi 2023. 2. 27. 23:45

https://leetcode.com/problems/construct-quad-tree/

Construct Quad Tree - LeetCode

Can you solve this real interview question? Construct Quad Tree - Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree. Return the root of the Quad-Tree representing the grid. Notice that you can assign the value of

leetcode.com

쿼드 트리 개념을 구현하는 문제.

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        return self.helper(grid, 0, 0, len(grid))

    def helper(self, grid, i, j, w):
        if self.allSame(grid, i, j, w):
            return Node(grid[i][j] == 1, True)
        
        node = Node(True, False)
        node.topLeft = self.helper(grid, i, j, w//2)
        node.topRight = self.helper(grid, i, j+w // 2, w//2)
        node.bottomLeft = self.helper(grid, i+w//2, j, w//2)
        node.bottomRight = self.helper(grid, i+w//2, j+w//2, w//2)

        return node

    def allSame(self, grid, i, j, w):
        for x in range(i, i+w):
            for y in range(j, j+w):
                if grid[x][y] != grid[i][j]:
                    return False
        return True