337. House Robber III

337. House Robber III

 

노드 2개가 연결된것을 선택하면 안된다는 거니,

=> 부모, 자식은 선택 못함,

즉,

1) 같은 레벨 끼리,

아니면,

2) 나를 기준으로, 내 부모->내 자식 요렇게

 

문제에서 요구하는 내용은 다음과 같습니다:

1. "부모-자식 관계에 있는 노드가 같은 날 털리지 않도록 해야 함":
   • 즉, 부모 노드와 직접 연결된 자식 노드 중 하나만 선택 가능.
   • 예를 들어, 한 노드를 선택하면 그 노드의 부모나 자식 노드는 선택할 수 없음.
2. "최대 금액을 구해야 함":
   • 각 노드의 값을 합산할 때 가능한 최대 금액을 계산.

---

해결 방법 (Dynamic Programming + Tree Traversal)

이 문제를 해결하기 위해 재귀적 접근법과 **DP (Dynamic Programming)**를 사용합니다.

• 아이디어:
  • 각 노드에서 두 가지 경우를 고려:
    1. 현재 노드를 선택하는 경우: 이 경우, 자식 노드는 선택할 수 없음(건너뜀).
    2. 현재 노드를 선택하지 않는 경우: 이 경우, 자식 노드를 선택할 수 있음.
  • 각 노드에서 두 가지 경우의 값을 계산한 뒤, 최댓값을 취합니다.

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        """
        문제 설명:
        도둑이 부모-자식 관계에 있는 두 노드를 같은 날 털게 되면 경찰에 알림이 전달됩니다.
        따라서, 부모와 자식 노드 중 하나만 선택 가능하며, 가능한 최대 금액을 계산해야 합니다.
        
        Problem Description:
        If the thief robs two directly-linked nodes (parent-child relationship) 
        on the same night, an alert will be sent to the police.
        Therefore, the thief can only rob either the parent or the child, but not both.
        The goal is to calculate the maximum amount of money that can be robbed.
        """

        # 하위 트리의 최대값을 구하는 재귀 함수
        # Recursive function to calculate the maximum amount for the subtree
        def dfs(cur_node):
            if not cur_node:
                # 노드가 없는 경우 (리프 노드의 자식 등) 0을 반환
                # (max_amount_with_cur_node, max_amount_without_cur_node)
                # 현재 노드를 포함한 경우와 포함하지 않은 경우의 최대값을 반환
                # If the node is null (e.g., a child of a leaf node), return 0.
                # Return a tuple: (max_amount_with_cur_node, max_amount_without_cur_node)
                return (0, 0)

            # 왼쪽과 오른쪽 자식 노드에 대해 재귀 호출
            # Recursively call for the left and right child nodes
            left = dfs(cur_node.left)
            right = dfs(cur_node.right)

            # 현재 노드를 선택하는 경우
            # When the current node is selected:
            # - 부모-자식 간의 제약으로 인해 자식 노드는 선택할 수 없습니다.
            # - 왼쪽 자식의 '노드 미선택' 값(left[1])과
            #   오른쪽 자식의 '노드 미선택' 값(right[1])을 합산합니다.
            # - Due to the parent-child constraint, child nodes cannot be selected.
            # - Add the current node value (cur_node.val) with the 'not selected' values
            #   from left[1] and right[1].
            max_amount_with_cur_node = cur_node.val + left[1] + right[1]

            # 현재 노드를 선택하지 않는 경우
            # When the current node is not selected:
            # - 현재 노드를 선택하지 않으면 자식 노드들은 자유롭게 선택할 수 있습니다.
            # - 각 자식 노드에서 선택 여부와 관계없이 최대값(max(left), max(right))을 가져옵니다.
            # - If the current node is not selected, child nodes can be freely selected.
            # - Take the maximum value from each child node (either selected or not).
            max_amount_without_cur_node = max(left) + max(right)

            # 현재 노드에서의 최대값 반환 (노드 선택 여부에 따른 두 가지 경우)
            # Return the maximum values for the current node, based on whether it is selected or not
            return (max_amount_with_cur_node, max_amount_without_cur_node)

        # 루트 노드에서부터 최대값을 계산
        # Start calculating from the root node
        # dfs(root)는 (루트 노드 선택 시 최대값, 루트 노드 미선택 시 최대값)을 반환합니다.
        # dfs(root) returns (max_amount_with_root, max_amount_without_root)
        # 이 중 최댓값을 결과로 반환합니다.
        # Return the maximum of the two values
        return max(dfs(root))

 

요약

• max_ammount_with_cur_node: 현재 노드를 선택하면 자식 노드는 선택하지 않습니다.
• max_ammount_without_cur_node: 현재 노드를 선택하지 않으면 자식 노드에서 최대 금액을 선택합니다.

이 방식으로 부모-자식 간 제약을 유지하며 최대 금액을 계산할 수 있습니다.