ch14-3(leetcode 687). 가장 긴 동일 값의 경로

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 687번 ( https://leetcode.com/problems/longest-univalue-path/ )

 

✅교재를 참고하지 않고 시도: DFS -> 실패

한 노드에 대해서 2개의 자식 노드가 있을 때, 해당 노드와 자식 노드의 값이 같을 때 DFS 탐색을 하고 값을 1씩 증가시키는 로직을 구현했다. 

 

3, 5 2개의 값이 연속되는 트리

 

그러나 위 그림처럼 여러 개의 값이 연속되는 트리가 입력으로 주어지면 중간에 다른 값이 나올 때는 DFS 탐색이 되지 않게 되어 오류가 발생한다. 

 

따라서 값이 연속되건 되지 않건 모든 경우에 DFS 탐색이 되어야 하고, 다만 노드와 자식 노드의 값이 같은지 다른지에 따라서 DFS 탐색을 한 값을 그대로 사용하거나 바꾸도록 구현해야 하겠다. 

 

class Solution(object):
    longest = 0

    def longestUnivaluePath(self, root):
        
        def dfs(node):

            if not node or (not node.left and not node.right):
                return 0

            left, right = 0, 0
            if node.left and node.val == node.left.val:
                left = dfs(node.left)
            if node.right and node.val == node.right.val:
                right = dfs(node.right)

            if left != 0 and right != 0:
                self.longest = max(self.longest, left + right + 2)
            elif left != 0:
                self.longest = max(self.longest, left)
            elif right != 0:
                self.longest = max(self.longest, right)
                
            return max(left, right) + 1

        result = dfs(root)
        return self.longest

 

✅교재를 참고해서 시도: DFS 

 

1. 클래스 변수 사용

교재에서도 DFS를 사용해서 진행하였다. 이전 문제와 같은 이유로 클래스 변수를 선언하고 가장 긴 동일값의 경로는 해당 변수에 저장하는 방법을 사용했다.

 

중첩 함수 내부에서 지역 변수를 사용하지 않은 이유는, '가장 긴 동일값의 경로'는 정수 형식이라서 불변 객체(immutable object)이고, 불변 객체인 변수는 중첩 함수의 내부에서 같은 이름으로 사용되더라도 값이 변경되지 않기 때문이다. 즉 중첩 함수 내부에서 값을 바꿔도 중첩 함수 바깥의 로컬 변수의 값이 변경되지 않는다. 

 

대신에 클래스 변수는 클래스 내부의 메소드에서 모두 공유되는 변수이므로 중첩 함수에서 변경하건, 바깥 함수에서 변경하건 클래스 변수의 값이 모두 변경된다. 

class Solution(object):
    longest = 0

    def longestUnivaluePath(self, root):
        // code

 

 

2. 모든 경우에 대해서 DFS 탐색을 하고 경우에 따라 세분화

DFS 탐색은 leaf 노드에 도달할 때까지 계속 자식 노드를 호출하다가 leaf 노드가 발견되면 여기서부터 탐색을 시작한다. 그러므로 leaf 노드에 도달했을 때 실행할 base case를 만들어 주자.

leaf 노드 하나에 대해서만 DFS 탐색을 실행한다고 가정하면 당연히 가장 긴 경로값은 0이므로 0을 리턴한다. 

if node is None:
    return 0

 

모든 경우에 대해서 DFS 탐색을 한다. 이때 이진 트리라서 왼쪽, 오른쪽 두 방향으로 탐색이 가능하므로 왼쪽 자식 노드와 오른쪽 자식 노드 모두에 대해서 각각 탐색을 진행한다. 

left = dfs(node.left)
right = dfs(node.right)

 

이때 left와 right는 각각 왼쪽, 오른쪽 자식 노드까지 DFS 탐색을 했을 때 가장 긴 경로를 나타낸다. 

이는 DFS 중첩 함수의 리턴값으로, 클래스 변수에 저장되는 값과는 다르다. 

 

DFS 중첩 함수의 리턴값은 leaf 노드에서부터 올라가면서 탐색을 시작하고, 계속 같은 값을 가진 노드가 나올 때마다 1씩 증가한다. 중간에 다른 값인 노드가 나오면 다시 0으로 초기화된다. 

if node.left and node.val == node.left.val:
    left += 1
else:
    left = 0
    
if node.right and node.val == node.right.val:
    right += 1
else:
    right = 0
    
return max(left, right)

 

반면 클래스 변수에 저장되는 값은 DFS 중첩 함수에서 리턴되는 값과 자기 자신을 계속 비교해서 더 큰 값을 저장한다. DFS 탐색 중 중간에 다른 값인 노드를 만나서 리턴값이 0으로 초기화되더라도 클래스 변수의 값은 초기화되지 않는다는 차이가 있다. 

self.longest = max(self.longest, left + right)