[DFS 문제 LV1] 숫자 삼각형 탐색 문제/코드

난이도 1 - 기본 탐색 (예상 소요 시간: 5~10분)

🔹 문제: 숫자 삼각형 탐색

 

n개의 줄로 이루어진 숫자 삼각형이 주어진다. 가장 위에서 시작해서 아래로 이동하며 합이 최대가 되는 경로를 찾으시오.
단, 한 번에 아래층의 바로 아래나 오른쪽 아래로만 이동할 수 있다.

 

입력 예시:

3  
7  
3 8  
8 1 0

 

 

출력 예시:

 

최대 합: 18 (7 → 8 → 3)

 

문제 설명

숫자로 이루어진 삼각형이 주어졌을 때, 위에서 아래로 이동하면서 얻을 수 있는 최대 합을 구하는 문제.
단, 이동할 때는 바로 아래 또는 오른쪽 아래로만 갈 수 있어.

 

입력 예제 2

 

4  
4  
2 3  
3 6 1  
8 2 7 4

출력 예제 2

 

최대 합: 18 (4 → 3 → 6 → 7)

경로 설명

1. 4 (첫 번째 줄)
2. 3 (두 번째 줄, 선택 가능: 2, 3 → 더 큰 값인 3 선택)
3. 6 (세 번째 줄, 선택 가능: 3, 6 → 더 큰 값인 6 선택)
4. 7 (네 번째 줄, 선택 가능: 8, 2, 7 → 더 큰 값인 7 선택)

이렇게 이동하면 4 → 3 → 6 → 7 = 18이 되고, 최대 합이 된다. 🚀

 

🔹 코드

function solution(n, arr) {
    let maximum = 0;

    function dfs(x, y, sum) {
        // 현재 위치의 값 더하기
        sum += arr[y][x];

        // 마지막 줄에 도달하면 최대값 갱신 후 종료
        if (y === arr.length - 1) {
            maximum = Math.max(maximum, sum);
            return;
        }

        // 아래쪽 이동 (가능한 경우)
        if (y + 1 < arr.length) {
            dfs(x, y + 1, sum); 
        }
        
        // 오른쪽 아래 이동 (가능한 경우)
        if (x + 1 < arr[y + 1].length) {
            dfs(x + 1, y + 1, sum);
        }
    }

    dfs(0, 0, 0);
    return maximum;
}

// 테스트
console.log(solution(3, [[7], [3, 8], [8, 1, 0]])); // 출력: 18