DFS - 재귀함수와 스택 프레임 / 아마존 기출 DFS 문제

재귀함수란?

함수가 자기 자신을 호출하는 것이다. 

 

재귀함수를 왜 쓸까? 

재귀함수는 반복이라는 면에서 for 문과 유사하다. 

하지만 for 문은 for 문이 완료되고 나면, 아래 예시처럼 자료구조에(ex. stack) 저장하지 않는 이상 이전 수행 코드의 정보를 사용할 수 없다. 재귀함수를 쓰면, 운영체제가 스택메모리에 정보를 저장하기 때문에 개발자가 따로 자료구조 구현을 하지 않아도 된다 (참고) 

Stack<Character> st = new Stack<>();    
for (char x : str.toCharArray()) {
         if (x == 'a')
            st.push(x);
 }

 

스택프레임이란?

스택 영역에 함수의 호출 정보가 쌓이는 것이다. 스택 영역에는 지역변수, 파라미터 등이 저장된다. 

StackOverFlow 에러는 DFS/재귀함수 구현 시 자주 볼 수 있는데, 스택 영역에 보관된 스택이 넘치는 현상이다. 

 

스택이 쌓인다는 것? 

해당 DFS 문제를 실행했을 때 스택 프레임의 모습이다. 

인텔리제이로 스택이 실행되는 것을 보면, 프레임에 스택이 쌓인다. 

처음에는 이게 객체가 쌓이는 건가? 헷갈렸었다. 하지만 해당 코드에서는 객체는 T 한 개만 생성했다.

DFSSubset2 T = new DFSSubset2();

함수를 여러번 호출한 것이다. 그러므로 객체는 하나로 동일하다. 

 

---

아래는 아마존 기출 DFS 문제다 (인프런 김태원 강사님 자바 알고리즘 합이 있는 부분집합)

 

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때

두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

예시 입력: 

6
1 3 5 6 7 10 //YES

답안 코드: 

 

public class DFSSubset2 {
    static String answer = "No"; //해당 코드에서 static method 에서 answer 출력하기 위해 static
    static int sum, n;
    boolean flag = false; 
    public void DFS(int L, int value, int[] arr){
        if (flag == true) return; //true 라면 이미 answer = Yes.
        if (value>sum/2) return; // value 가 더 크다면, 더 계산할 필요가 없다.
        //값을 찾는다면, 여기서 flag 를 표시해주고. 아닐 경우는 재귀를 타고 내려가기.
        //이 문제는 DFS 이고, 처음부터 끝까지 경우의 수 탐색 
        if(L==n){
            if(sum%2==0 && value == sum/2){ //홀수이면 안되기 때문.
                answer = "YES";
                flag = true;
            }
        }

        else {
            DFS(L+1, value+arr[L], arr); //(꼭 arr 전체가 아니라, o/x 유무가 가려지는 해당 원소값만 들어가도 됨. 여기서 중요한 것은 합.
            DFS(L+1, value, arr);
        }
    }

    public static void main(String[] args){
        DFSSubset2 T = new DFSSubset2();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n;i++){
            arr[i] = sc.nextInt();
            sum+=arr[i];
        }
        T.DFS(0, 0,arr);
        System.out.println(answer);
    }
}

 

DFS 는 해당 원소의 유/무를 기준으로 자기 자신을 호출하면서, 트리 구조를 그리며 내려간다.

아래 코드에서 value는 DFS 를 내려가면서, 해당 위치에서 계산한 총합을 말한다

value가 주어진 집합의 총합의 절반보다 크면, 자기 자신과 합이 같은 부분집합이 없다는 뜻이다.  

 

이때 왜 return 을 쓰는 걸까? 이 상태에서 함수를 exit 하면 오답아닐까? 라고 생각했었다

아래는 (1,3,5,6,10)일 때, value는 25이고 sum 32의 절반인 16보다 크다. 

그럼 여기서 함수가 종료되고 answer = "No"를 출력하며 끝날까? 

당연히 스택프레임을 공부하신 분은 아시겠지만 재귀함수는 자기 자신을 호출하며 스택 프레임에 쌓인다.  return 을 해도  DFS 가 종료되지 않았다면 이전 스택으로 포인터가 넘어간다 (EX.중괄호가 닫히기 전에 다른 DFS를 불러온 경우) 

재귀함수를 쓰지 않는 경우는 return 시 함수가 종료되고, main 함수도 종료되는 모습을 자주 보았기에, 이 부분이 특히 헷갈렸던 것 같다. 

 

위의 화면에서 인텔리제이에 브레이킹 포인트를 찍고 실행했을 때, 바로 다음 장면이 아래와 같다. 

우선 value>sum/2 를 거친다음 7번째 스택은 바로 종료된다. 

기존 원소인 10이 빠진 (arr[L]이 빠진 (1,3,5,6) 이다.

기존 스택: 1o,3o,5o,6o,7x10o (레벨 6)

바로 한 단계 이전에 실행되었을 현재 6번째 스택은 1o,3o,5o,6o,7x. 10을 아예 거치지 않아서 레벨이 5임을 확인할 수 있다. 

 

 

다음은 VALUE 가 16일 때 (32/2 = 16이기 때문에, answer 가 Yes 가 되는 순간이다) 의 스택 프레임이다. 

단, flag 가 true 이기 때문에 윗 줄에서 RETURN 을 만나고 해당 DFS 가 종료된다. 

 

 

---

참고: 

return은 메서드를 빠져나가고,

break 는 반복문을 빠져나간다. 

continue는 반복문의 해당 횟수 빠져나가서 다음으로 넘어간다.

int x = 1;
while(x<3){
    x++;
    if(x==1) continue; //while 문으로 돌아가고 
    if(x==2) break; // 조건문을 여기서 종료한다. 

}

 

풀이 출처: https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/lecture/73396?tab=note&volume=0.83