427. Construct Quad Tree

427. Construct Quad Tree

 

https://youtu.be/UQ-1sBMV0v4?si=5BBkFUGx3Q4HoIeF

 

"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val  # 현재 노드의 값 (0 또는 1)
        self.isLeaf = isLeaf  # 현재 노드가 리프 노드인지 여부
        self.topLeft = topLeft  # 왼쪽 위 서브노드
        self.topRight = topRight  # 오른쪽 위 서브노드
        self.bottomLeft = bottomLeft  # 왼쪽 아래 서브노드
        self.bottomRight = bottomRight  # 오른쪽 아래 서브노드
"""
# Solution 클래스 정의
class Solution:
    # 주어진 2D 그리드(grid)를 쿼드 트리로 변환하는 함수
    def construct(self, grid: List[List[int]]) -> 'Node':
        # dfs 함수 정의: (격자의 크기 n, 시작 행 r, 시작 열 c)
        def dfs(n, r, c):
            # 현재 격자 내 값이 모두 동일한지 확인하는 플래그
            allSame = True

            # 격자의 모든 값을 순회하며 값 비교
            for i in range(n):
                for j in range(n):
                    # 만약 값이 하나라도 다르면 allSame을 False로 설정하고 중단
                    if grid[r][c] != grid[r+i][c+j]:
                        allSame = False
                        break
            # 격자의 모든 값이 동일하다면 리프 노드로 생성
            if allSame:
                return Node(grid[r][c], True, None, None, None, None)

            # 격자를 4개의 하위 격자로 나누기 위한 절반 크기 계산
            halfn = n // 2
            # 왼쪽 위 부분 격자 처리
            topleft = dfs(halfn, r, c)
            # 오른쪽 위 부분 격자 처리
            topright = dfs(halfn, r, c + halfn)
            # 왼쪽 아래 부분 격자 처리
            bottomleft = dfs(halfn, r + halfn, c)
            # 오른쪽 아래 부분 격자 처리
            bottomright = dfs(halfn, r + halfn, c + halfn)

            # 리프 노드가 아니므로 isLeaf는 False, val은 임의 값(여기서는 0 사용)
            return Node(0, False, topleft, topright, bottomleft, bottomright)

        # 전체 격자를 대상으로 DFS 수행 시작 (크기: len(grid), 시작 좌표: (0, 0))
        return dfs(len(grid), 0, 0)

 

상세 설명

1. Node 클래스 정의:
   • 쿼드 트리의 각 노드는 val, isLeaf, topLeft, topRight, bottomLeft, bottomRight를 가집니다.
   • val: 노드의 값 (리프 노드일 경우 격자의 값을 가짐).
   • isLeaf: 현재 노드가 리프 노드인지 여부를 나타냄.
   • topLeft, topRight, bottomLeft, bottomRight: 하위 4개 격자에 대한 자식 노드.
2. construct 함수:
   • 2D 격자를 받아 쿼드 트리로 변환.
   • 내부적으로 dfs 함수 호출.
3. dfs 함수:
   • 매개변수:
     • n: 현재 처리 중인 격자의 크기.
     • r: 현재 격자의 시작 행.
     • c: 현재 격자의 시작 열.
   • 작동 방식:
     1. 현재 격자가 모두 동일한 값인지 확인:
        • 격자의 첫 번째 값(grid[r][c])과 나머지 값을 비교.
        • 모든 값이 동일하면 Node(grid[r][c], True)를 생성.
     2. 모두 동일하지 않으면 격자를 4개로 나눔:
        • 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 격자에 대해 재귀 호출.
        • 각각의 결과를 topLeft, topRight, bottomLeft, bottomRight로 저장.
     3. 리프 노드가 아니므로 Node(0, False, ...)를 생성.
4. halfn 계산:
   • 격자를 나누기 위한 절반 크기를 계산 (n // 2).
5. 재귀 호출의 종료 조건:
   • 격자가 모두 동일한 값을 가지면 리프 노드를 반환하여 종료.

 

 

리프 노드(Leaf Node)가 끝 노드인지?

**리프 노드(Leaf Node)**는 트리 구조에서 더 이상 자식 노드가 없는 노드를 의미합니다.

따라서, 리프 노드는 트리의 끝 부분에 위치한 노드라고 할 수 있습니다.

---

쿼드 트리에서의 리프 노드

1. 리프 노드의 정의:
   • 쿼드 트리에서는 현재 격자가 모두 동일한 값을 가질 경우, 해당 노드를 리프 노드로 생성합니다.
   • 이 리프 노드는 더 이상 4개의 하위 격자로 나뉘지 않으며, 트리의 말단(끝)에 위치합니다.
2. 리프 노드의 특징:
   • **isLeaf = True**로 표시됩니다.
   • 값(val)은 격자의 값을 나타냅니다 (예: 0 또는 1).
   • 자식 노드(topLeft, topRight, bottomLeft, bottomRight)는 모두 None입니다.

정리

• 리프 노드는 쿼드 트리에서 더 이상 나뉘지 않는 끝 노드입니다.
• 리프 노드는 항상 isLeaf = True로 표시되며, 자식 노드가 없습니다.
• 쿼드 트리에서는 격자가 모두 동일한 값일 때 리프 노드가 생성됩니다.