[DFS] 2. 바둑이 승차

<<풀이>>

 

 

-나의 풀이- 

 

아직 익숙하지 않은 탓인가 ?? 문제는 쉬워 보였고 실제로도 그렇게 어렵지 않게 풀이를 만들었는데, 논리적으로 맞는거 같지만 그러하지 못하고 틀렸다 ㅠㅠ

 

일단 나는 각 자리 수를 더한다 아니면 더 하지 않는다 이렇게 경우의 수를 두고 진행했다.

import java.util.ArrayList;
import java.util.Scanner;

class Main {
    static int answer;
    static ArrayList<Integer> list = new ArrayList<>();;


    private void DFS(int L, int maxNum, int[] arr) {


        if (answer > maxNum) {
            answer -= arr[L - 1];
            list.add(answer);
            return;
        } else {
            if(L > arr.length - 1) return;
            answer += arr[L];
            DFS(L + 1, maxNum, arr);
            answer -= arr[L];
            DFS(L + 1, maxNum, arr);
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int maxNum = in.nextInt();
        int total = in.nextInt();
        int[] arr = new int[total];

        for (int i = 0; i < total; i++) {
            arr[i] = in.nextInt();
        }

        T.DFS(0, maxNum, arr);
        int max = 0;
        for (int x : list) {
            if (max <= x) max = x;
        }

        System.out.println(max);

    }
}

 

 

-강사님 풀이-

 

아 맞다 이렇게 하면 되는구나 ~~ 하고 있다 ㅋㅋ

 

<<풀이 접근 방식>>

이 문제의 핵심 풀이법은 2^n 이다. 합할까 합하지 않을까 이렇게 2가지로 계속 내려온다. 그래서 결과값의 갯수는 원래 총 2^n 이다.

근데, 범위 내의 값을 가져오는 조건이 있기 때문에 그 조건에 해당하지 않으면 빼는 것 뿐이다. 이러한 논리구조로 푼다면 쉽게 접근이 가능하다.

 

<<구조적 접근 방식>>

DFS의 매개변수에 sum을 넣는 방식을 사용하고 있다.

전체적인 구조는 재귀함수로서 돌기 때문에 그 다음 재귀함수가 진행이 될때, 조건으로 성립하는지 먼저 판 별한 후에 그 다음 식을 진행한다.

여기서 나는 sum + arr[L] 하고 return해서 돌아오면, 뭔가가 sum에 대한 내용이 바뀔거 같지만, 

조건을 충족하고  Math.max 안 에 넣고 거기에 대한 반환값이 answer 에 다시 넣어줄 때 비로소 반영이 된다. 

 

*주로 DFS문제는 if가 있고 그 다음 DFS가 있다.

import java.util.Scanner;

class Main {
    static int answer, c, n;

    private void DFS(int L, int sum, int[] arr) {
        if (sum > c) return; // 필터 역할을 하고 있네
        if (L == n)  {
            answer = Math.max(sum, answer);
        } else {
            DFS(L+1, sum + arr[L], arr);
            DFS(L+1, sum , arr);
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        c = in.nextInt();
        n = in.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        T.DFS(0, 0, arr);
        System.out.println(answer);
    }
}

 

이번 문제를 풀면서 머릿속으로 하니깐 이해도 면에서 긴가민가한 거 같다 ㅋㅋ

 

이 문제를 직접 그려보면서 다시 봐야겠다 !!

 

 

추가 공부로 직접 그려보았다. 역시 그려보니까 훨씬 이해가 잘 된다. DFS 와 BFS는 머리로만 파악하기에 한계가 있다.

 

따라서, 이를 직접 그려보고 판단하자!!