DFS에서 값을 반환하는 3가지 패턴: 누적, 비교, 조건 반환

DFS에서 int 값을 반환하고자 할 때는 보통 다음 두 가지 상황 중 하나입니다:

1. 재귀적으로 값을 누적해서 최종 결과를 반환하는 경우
   예: 경로 수, 최대/최소 값, 점수 합산 등
2. 재귀 과정에서 특정 값을 탐색하고, 그걸 상위로 전달하는 구조
   예: 최대 점수 등
3. 특정 조건이 맞으면 바로 값을 반환하고 전파 : 조기 반환
   예: 특정 노드 존재 여부, 경로 찾기 

---

패턴 1. 누적 반환 (Aggregation)

하위 노드들의 값을 더하거나 합쳐서 상위로 반환하는 방식입니다.

✅ 사용 상황

• 리프 노드 개수 세기
• 특정 조건을 만족하는 노드 개수
• 총합 계산

✅ 예제 코드: 리프 노드 개수 구하기

public class Main {
    public static void main(String[] args) {
        // 예시 트리
        List<Integer>[] tree = new ArrayList[5];
        for (int i = 0; i < 5; i++) tree[i] = new ArrayList<>();
        tree[0].add(1);
        tree[0].add(2);
        tree[1].add(3);
        tree[1].add(4);

        boolean[] visited = new boolean[5];
        int leafCount = dfs(0, tree, visited);
        System.out.println("리프 노드 수: " + leafCount);
    }

    static int dfs(int node, List<Integer>[] graph, boolean[] visited) {
        visited[node] = true;
        boolean isLeaf = true;
        int total = 0;

        for (int next : graph[node]) {
            if (!visited[next]) {
                isLeaf = false;
                total += dfs(next, graph, visited);  // 자식의 리프 개수를 누적
            }
        }

        if (isLeaf) return 1; // 자식이 없다면 자신이 리프 노드
        return total;         // 자식의 리프 개수를 반환
    }
}

---

패턴 2. 비교 반환 (Selection)

하위 결과 중에서 최대/최소/최선의 값을 선택해 반환합니다.

✅ 사용 상황

• 가장 긴 경로 찾기
• 최대/최소 점수 계산
• 최댓값, 최솟값 누적

✅ 예제 코드: 최대 노드 값 찾기

static int dfs(int node, List<Integer>[] graph, boolean[] visited, int[] values) {
    visited[node] = true;
    int maxValue = values[node];  // 현재 노드 값으로 초기화

	for (int next : graph[node]) {
        if (!visited[next]) {
            maxValue = Math.max(maxValue, dfs(next, graph, visited, values));
        }
    }
    return maxValue;
}

---

패턴 3. 조건 반환 (Early Return)

탐색 도중 특정 조건을 만족하면 즉시 값을 반환하고 더 이상의 탐색을 생략합니다.

✅ 사용 상황

• 특정 값이나 노드를 찾았는지 여부 확인
• DFS 경로 중 특정 조건 만족 시 탐색 조기 종료

✅ 예제 코드: 특정 값이 있는지 찾기

int dfs(int node, int target, List<Integer>[] graph, boolean[] visited, int[] values) {
    visited[node] = true;
    if (values[node] == target) return 1;

    for (int next : graph[node]) {
        if (!visited[next]) {
            int result = dfs(next, target, graph, visited, values);
            if (result == 1) return 1;  // 찾았으면 바로 전파
        }
    }

    return 0; // 못 찾았을 경우
}

---

🧭 요약

패턴	설명	대표 예시
누적 반환	하위 결과를 더하거나 합치는 방식	리프 노드 개수, 경로 수, 총합
비교 반환	최대/최소/최선의 값을 선택	최대값, 최소 거리, 최고 점수
조건 반환	조건 만족 시 즉시 탐색 종료	경로 존재 여부, 조건 탐색