[Java/Algorithm] DFS - 포화 이진 트리에서 최소 경로 합

문제 설명

2차원 배열로 추어지는 포화 이진트리에서 루트 노드부터 리프 노드까지의 경로 중 합이 가장 작은 값을 반환한다.

예시

int[][] A = {
            {1},
            {2, 5},
            {7, 10, 1},
            {9, 4, 4, 5}
        };

• 예시 트리에서 최소 경로 합은 1 → 2 → 7 → 4로 14가 된다.

풀이 과정

포화 이진 트리는 각 레벨마다 노드가 완전히 채워져 있다는 특징이 있습니다. 항상 자식 노드가 두 개이기 때문에 존재 여부를 매번 확인할 필요가 없습니다. 마지막 레벨은 모든 노드가 리프 노드이므로 언제 탐색을 종료해야 할지가 명확합니다.

이 문제는 최소 경로 합을 구하는 것이 목적이기 때문에, 어떤 경로가 최종적으로 최소값을 반환할 지 판단하기 위해서는 경로를 끝까지 탐색해서 계산하고 비교해야 합니다.

BFS는 큐를 사용해서 각 레벨에 있는 모든 노드를 탐색합니다. 전체 트리를 모두 탐색하는 것을 목표로 둔다면 유리한 알고리즘입니다. (지난 문제 풀이 참고)

반면, DFS는 스택에 탐색 중인 노드만 저장하고 재귀 호출 (깊이 탐색, 하위 탐색)로 다음 노드로 이동합니다. 그 후 스택에 넣은 값을 후입선출 방식으로 꺼내면서 상위 메소드에 반환하는 과정을 거칩니다. (상위 탐색)

이 방식은 현재 경로에 있는 노드만 메모리에 저장하기 때문에 메모리 사용량이 적습니다. 전체 트리를 탐색하는 것보다 하나의 최적화된 경로를 찾는 것을 빠르게 발견하는 게 목표인 경우에 더 적합한 알고리즘입니다.

이번 문제는 특정 경로의 리프 노드까지 빠르게 탐색하는 것을 우선 순위 목표로 두고, 각 경로의 최종값이 나올 때마다 비교를 진행하는 방식으로 풀 수 있었습니다.

1. DFS에 메소드에 필요한 인자를 받는다
탐색과 재귀 호출에 사용될 dfs 메소드를 만들어 줍니다. 필요한 인자는 아래와 같습니다.

• int[][] A: 포화 이진 트리를 구성하는 2차원 배열
• int level: 탐색을 시작할 레벨 지정
• int index: 탐색을 시작할 인덱스 지정

탐색을 위해서는 기본적으로 위에 3가지가 필요하고, 이 문제에서는 경로의 합을 누적해서 구해야하기 때문에 아래 인자를 추가해 줍니다.

• int currentSum: 현재 탐색하고 있는 경로의 합

private int dfs(int[][] A, int level, int index, int curSum) {
...

2. 현재 노드를 더하고 리프 노드인지 확인한다
이 메소드는 먼저 현재 탐색 중인 노드 값을 총 합에 누적해야 합니다.

curSum += A[level][index];

만약 현재 탐색 중인 노드가 마지막 레벨에 존재한다면 더 이상 탐색이 필요하지 않습니다. 현재까지 더한 값을 반환하고 탐색을 종료할 수 있는 코드를 작성합니다.

if (level == A.length - 1) {
	return curSum;
}

3. 자식 노드가 있다면 해당 경로로 재귀 호출(하향 탐색)을 진행한다
마지막 레벨이 아니라면 자식 노드 2개가 반드시 존재한다는 뜻이므로, 각각의 경로로 탐색을 이어갈 수 있도록 현재 메소드를 재귀 호출합니다.

int leftSum = dfs(A, level + 1, index, curSum);
int rightSum = dfs(A, level + 1, index + 1, curSum);

이 과정은 리프 노드에 도달할 때까지 계속됩니다.

4. 다시 상위 탐색 진행으로 최소 경로 합 반환

1️⃣ leftSum에 재귀 호출로 왼쪽 자식 노드 값 반환:

• 왼쪽 자식 노드로 재귀 호출을 해서, 해당 노드를 거쳐간 경로의 최소 합 계산
• 바로 위 부모 노드에 그 값을 반환

2️⃣ rightSum에 재귀 호출로 오른쪽 자식 노드 값 반환:

• 바로 옆 형제 노드인 오른쪽 자식 노드로 재귀 호출 해서, 해당 노드를 거쳐간 경로의 최소 합 계산

3️⃣ 반환 된 두 값을 비교해서 부모 노드에 반환

• 두 자식 노드 값을 반환 받은 부모 노드에서 Math.min()으로 비교 후 저장
• 이제 이 부모 노드가 상위 부모 노드의 (왼쪽) 자식 노드로 재귀 호출에 포함되기 때문에, 방금 저장한 값을 상위 부모 노드에 반환

int leftSum = dfs(A, level + 1, index, curSum); 이 코드에서leftSum은 level을 내려가고 index는 그대로이므로, 부모 노드와 왼쪽 자식 노드는 index가 동일합니다. 즉, 재귀 호출 후 상위 탐색을 진행할 시 현재 부모 노드는 상위 부모 노드의 왼쪽 자식 노드가 됩니다.

이렇게 모든 반복이 끝나면 루트 노드에 가장 작은 경로 합이 저장되어 문제에서 원하는 값을 반환할 수 있습니다.

전체 코드

class Solution {
    public int solution(int[][] A) {
        // 포화 이진 트리에서 DFS 수행
        return dfs(A, 0, 0, 0);
    }

    private int dfs(int[][] A, int level, int index, int curSum) {
        curSum += A[level][index];

        if (level == A.length - 1) { // 리프노드면 반환
            return curSum;
        }

        int leftSum = dfs(A, level + 1, index, curSum); // 왼쪽 자식 노드 값 반환 후
        int rightSum = dfs(A, level + 1, index + 1, curSum); // 오른쪽 자식 노드 값 반환

        return Math.min(leftSum, rightSum); // 둘 중 더 작은 값을 부모 노드가 갖고, 현재 부모 노드가 자식 노드가 되어 상위 부모 노드에 값 반환 과정을 반복
    }
}