2022/03/31) 6. 바둑이 승차 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<바둑이 승차>
: 철수는 그의 바둑이를 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성한다.

2. 해결 방법

1. 이전에 배운대로 태울 것인가(포함) 태우지 않을 것인가(불포함)으로 따지면 된다. 다만 다른 점은 sum이 트럭무게를 넘느냐 안넘느냐를 확인해야 하고, 최대sum을 구해야 한다는 점이다.
2. 흐름을 보기 위해서 코드를 순차적으로 올렸다. 콘솔창에서 어떤 순서로 출력되는지를 확인하라.
   맨 마지막게 정답이다.

3. 정답

        <script>
            function solution(c, arr){
                let answer = 0;
                let n = arr.length;
                    function DFS(L, sum){
                        if(L===n){ //L이 n일 때, 부분집합 하나가 완성된다.
                            console.log(sum);
                            answer = Math.max(answer, sum);
                        }
                        else{
                            DFS(L+1, sum+arr[L]); //포함
                            DFS(L+1, sum); //불포함
                        }
                    }
                DFS(0, 0);
                return answer;
            }
            let arr=[81, 58, 42, 33, 61];
            console.log(solution(259, arr));
        </script>

        <script>
            function solution(c, arr){
                let answer = 0;
                let n = arr.length;
                    function DFS(L, sum){
                        if(sum>c) return;
                        if(L===n){ 
                            console.log(sum);
                            answer = Math.max(answer, sum);
                        }
                        else{
                            DFS(L+1, sum+arr[L]); 
                            DFS(L+1, sum); 
                        }
                    }
                DFS(0, 0);
                return answer;
            }
            let arr=[81, 58, 42, 33, 61];
            console.log(solution(259, arr));
        </script>

        <script>
            function solution(c, arr){
                let answer = 0;
                let n = arr.length;
                    function DFS(L, sum){
                        if(sum>c) return; //가지치기!! 밑에 if-else문에 못감!
                        if(L===n){ 
                            answer = Math.max(answer, sum);
                        }
                        else{
                            DFS(L+1, sum+arr[L]); 
                            DFS(L+1, sum); 
                        }
                    }
                DFS(0, 0);
                return answer;
            }
            let arr=[81, 58, 42, 33, 61];
            console.log(solution(259, arr));
        </script>

4. 내 코드와 비교 그리고 반성

이제 좀 감이 온다. 포함인지 불포함인지가 핵심인 거 같다. 이제 어떻게 줄기가 이어나가는지만 확실히 이해해서, if문만 잘 작성하면 된다. 그리고 ! 왜 L===n인지 이해못했었는데 이제 이해했다! 포함이든 불포함이든 모든 인덱스를 돌아서 0혹은 X를 해줘야 하기 때문이다. L===n일 때, 부분집합 하나가 완성되는 것이다!