연속 증가 경로의 최대 길이 구하기

트리 문제를 풀다 보면 막히는 순간이 있습니다.

"어디서부터 생각해야 하지?" 싶은 순간인데, 이 문제는 그 감각을 연습하기 좋습니다.

겉으로 보면 경로 길이를 세는 문제처럼 보이지만, 실제로는 현재 노드가 부모에게 어떤 값을 넘겨줘야 하는지를 정해야 풀리는 유형입니다.

문제

이진 트리의 루트가 주어질 때, 부모에서 자식으로 내려가면서 값이 정확히 1씩 증가하는 경로의 최대 길이를 구하면 됩니다.

여기서 경로는 반드시 위에서 아래로만 이어져야 하고, 부모 값이 x라면 자식 값은 x + 1이어야 합니다.

길이는 경로에 포함된 노드 수로 계산합니다.

예를 들어 아래와 같은 트리가 있다고 하겠습니다.

이 트리에서 가장 긴 연속 증가 경로는 3 -> 4 -> 5 -> 6 이므로 정답은 4입니다.

즉, 단순히 더 큰 값으로 가는 것이 아니라 바로 다음 숫자여야만 이어 붙일 수 있습니다.

처음 떠오르는 생각

처음에는 모든 노드를 시작점으로 잡고 아래로 쭉 따라가면 될 것처럼 보입니다.

하지만 그렇게 하면 같은 하위 경로를 여러 번 다시 계산하게 됩니다.

즉, 이 문제의 핵심은 단순 탐색보다 중복 계산을 줄이면서 부모가 쓸 수 있는 정보를 정리하는 것입니다.

핵심 아이디어

현재 노드에서 부모에게 넘겨줄 정보는 사실 하나면 충분합니다.

현재 노드에서 시작해서 아래로 내려갈 때, 만들 수 있는 연속 증가 경로의 최대 길이

이 값만 알면 부모는 어느 자식 경로를 이어 붙일 수 있는지 판단할 수 있습니다.

그래서 재귀 함수 dfs(node)를 아래처럼 두면 흐름이 깔끔합니다.

dfs(node) = node에서 시작하는 연속 증가 경로의 최대 길이

현재 노드에서는 다음 순서로 생각하면 됩니다.

왼쪽 자식 결과를 받는다
오른쪽 자식 결과를 받는다
현재 값과 자식 값 차이가 정확히 +1인지 확인한다
이어질 수 있다면 길이를 늘린다
현재 노드 기준 최대 길이를 부모에게 반환한다

트리 전체에서 가장 큰 값은 별도의 변수 answer로 관리하면 됩니다.

코드

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def longest_increasing_path(root):
    if root is None:
        return 0

    answer = 0

    def dfs(node):
        nonlocal answer

        if node is None:
            return 0

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

        current_len = 1

        if node.left and node.left.val == node.val + 1:
            current_len = max(current_len, 1 + left_len)

        if node.right and node.right.val == node.val + 1:
            current_len = max(current_len, 1 + right_len)

        answer = max(answer, current_len)
        return current_len

    dfs(root)
    return answer

코드 해설

빈 노드는 길이 0으로 본다

if node is None:
    return 0

노드가 없으면 만들 수 있는 경로도 없습니다.

그래서 길이 0을 반환하면 됩니다.

왼쪽과 오른쪽 결과를 먼저 받는다

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

현재 노드를 바로 판단하는 것이 아니라, 먼저 아래쪽에서 만들 수 있는 증가 경로 길이를 계산합니다.

기본 길이는 자기 자신만 포함한 1이다

current_len = 1

아무 자식과도 연결되지 않더라도 현재 노드 하나만으로 길이 1짜리 경로는 만들 수 있습니다.

자식 값이 정확히 1 크면 이어 붙일 수 있다

if node.left and node.left.val == node.val + 1:
    current_len = max(current_len, 1 + left_len)

if node.right and node.right.val == node.val + 1:
    current_len = max(current_len, 1 + right_len)

예를 들어 현재 노드가 4이고 자식이 5라면, 현재 노드에서 시작하는 증가 경로에 자식 결과를 붙일 수 있습니다.

반대로 자식이 6이면 안 됩니다.

이 문제는 단순 증가가 아니라 정확히 1 증가가 조건이기 때문입니다.

전체 최대값은 따로 갱신한다

answer = max(answer, current_len)

dfs(node)가 반환하는 값은 현재 노드에서 시작하는 최대 길이이고, answer는 트리 전체에서의 최대 길이입니다.

이 둘을 분리해 두면 코드가 훨씬 덜 헷갈립니다.

실행 예시

root = Node(
    3,
    Node(
        4,
        Node(5, Node(6)),
        Node(3)
    ),
    Node(
        2,
        None,
        Node(3)
    )
)

print(longest_increasing_path(root))  # 4

복잡도

시간 복잡도 — O(n)
공간 복잡도 — O(h)

모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다.

추가 공간은 재귀 호출 스택 때문에 트리 높이 h만큼 필요합니다.

균형 트리면 대략 O(log n)
한쪽으로 치우친 트리면 최악의 경우 O(n)

실수하기 쉬운 부분

단순히 더 큰 값이면 되는 게 아니다

4 -> 6은 증가이긴 하지만 이 문제에서는 실패입니다.

반드시 정확히 1 증가여야 합니다.

왼쪽과 오른쪽을 합치면 안 된다

이 문제는 현재 노드에서 시작해 한 방향으로만 이어지는 경로를 봅니다.

즉 왼쪽으로 2칸, 오른쪽으로 3칸이 나온다고 해서 둘을 합쳐 5로 만들 수는 없습니다.

반환값과 전체 정답은 다르다

dfs(node)가 돌려주는 값은 현재 노드에서 시작하는 최대 길이입니다.

반면 answer는 트리 전체에서의 최대 길이입니다.

이 둘을 섞기 시작하면 재귀가 바로 꼬이기 쉽습니다.

정리

이 문제의 핵심은 현재 노드가 부모에게 어떤 값을 반환해야 하는지 정하는 것입니다
dfs(node)의 반환값과 전체 정답 answer는 분리해서 생각해야 합니다
단순 증가가 아니라 정확히 1 증가라는 조건을 놓치면 안 됩니다

트리 문제에서 이 감각이 잡히면 비슷한 DFS 유형이 훨씬 편해집니다.

비슷한 유형의 트리 DFS 문제를 공부하면서, 조건을 바꿔 직접 다시 구성해본 예제입니다.