[Leetcode] 337. House Robber III

21-12-05
Solved

Problem

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

대표적인 dp 유형 문제인 도둑질 문제다. 이번에는 BST에서 도둑질한다. 문제 가정이 조금 웃기다.

Solution

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        
        def goDFS(node) -> tuple:
            if not node:
                return (0,0)

            if not node.right and not node.left:
                return (node.val,0)
            
            le1,le2=goDFS(node.left)
            ri1,ri2=goDFS(node.right)
            
            return (max(node.val+le2+ri2,le1+ri1),le1+ri1)
            
            
        dp1,dp2=goDFS(root)
        
        
        
        return max(dp1,dp2)

처음에 잘못된 풀이로 갔다가,거기서 발생하는 오류에서 아이디어를 얻어 다음과 같이 풀이 방법을 생각해냈다. 이 문제를 풀기 전에 반드시 198. House Robber를 푸는 것을 권장한다. BST를 탐색하지 않고 array를 탐색하는 문제인데, 이러한 도둑질 유형 문제의 프로토타입이라고 할 수 있기 때문이다.

우선 기본적으로 트리를 DFS 방식으로 traversing한다. 그리고 goDFS에서 올라올 때마다 튜플로 두 가지 값을 전달한다.
(dp1, dp2)라고 하자. dp1은 leaf에서 방금 탐색한 노드까지의 최대합이다. dp2는 leaf부터 방금 탐색한 노드의 자식까지의 최대합이다. (198번 문제에서 dp를 array로 설정했다면 dp1은 dp[i], dp2는 dp[i-1]에 대응한다.)

return (max(node.val+le2+ri2,le1+ri1),le1+ri1)

이 때 goDFS가 다음과 같은 리턴값을 가지는 것이 핵심이다. dp1에서 node.val+le2+ri2가 더 크다는 말은 node의 val를 포함하고 node의 자식을 건너뛴 그 아래 자식들과 합을 선택하겠다는 의미이다. le1+ri1은 node를 포함하지 않아도 최대합을 만들 수 있다는 이야기다. dp2는 leaf에서 node의 자식단계까지의 최대 합이므로 le1+ri1이 되는 것은 명확하다.

return (node.val+le2+ri2,le1+ri1)

처음에 이렇게 코드를 짰다가, 테스트 코드에서 에러가 났다. 이렇게 코드를 짤 경우 다음과 같은 상황을 고려하지 못한다. 2-1-1-4 인 경우 (4가 루트이고 자식을 하나씩 가지는 경우), 정답은 2+4=6이 되어야 한다. 하지만 위와 같은 코드는 (2+1) , (1+4)만 고려하기 때문에 오답을 리턴한다. 이러한 유형에서 대표적으로 생각해줘야하는 케이스인 (선택하고, 안하고, 안하고, 다시 선택하는) 케이스를 반영하지 못하게 된다.

Wrong Solution

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        
        if not root:
            return 0
        
        if not root.right and not root.left:
            return root.val
        
        
        leftVal= self.rob(root.left)
        rightVal=self.rob(root.right)
        notSelect=leftVal+rightVal
        
        select=root.val
        if root.left:
            select+=self.rob(root.left.right)
            select+=self.rob(root.left.left)
        if root.right:
            select+=self.rob(root.right.right)
            select+=self.rob(root.right.left)
        
        return max(notSelect,select)

처음에 시도했던 잘못된 풀이이다. 테스트 케이스 122/124를 맞은 것을 보니 로직 자체로는 문제가 없다. 하지만 time limit excess error가 난다. 위 풀이는 tree의 특성 상 재귀함수를 이용해서 풀려고 시도한 것이다. 그런데 같은 node가 rob에서 중복으로 호출되어서 쓸데없는 연산을 반복적으로 하게 된다. (dynamic programming이 아니다.)