[알고리즘] 재귀와 깊이 우선 탐색(DFS)

알고리즘 문제를 풀다가 재귀를 사용하는 방법이 흥미로워 정리해 놓으려 합니다.

 

이전 글에서 짧고 부족한 재귀를 이해하는 설명을 했습니다. 이번에는 여러 선택지가 있는 재귀에서 후퇴하는 방법입니다.

 

앞선 글에서 피보나치 수열을 예시로 설명을 했습니다.

그리고 이 수열의 표현식을 '점화식'이라고 하죠.

N번째 항의 값은 그 이전 항(들)의 어떠한 로직으로 표현됩니다.

 

그런데 알고리즘에서는 이러한 일종의 점화식도 있습니다.

N번째 항의 값은 N-1번째에 어떤 로직을 수행해서 이뤄지는데, 어떤 로직의 경우의 수가 2개 이상입니다.

 

예를 들어보겠습니다.

좋은 바코드 문제입니다.

1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 이 바코드를 만드는 데에 조건이 걸려 있습니다. 바코드에서 인접한 두 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성하세요.

여기서 인접한 두 부분 수열의 예를 들어보겠습니다.

'1231' -> [1, 2]  [2, 3]  [3, 1]  [12, 21]

'12312' -> [1, 2] [2, 3] [3, 1] [1, 2] [12, 31] [23, 12]

 

이 문제는 맨 앞의 수부터, 다시말하면 0번 인덱스부터 주어진 조건을 만족하면서 채워나가면 됩니다. 같은 로직이 반복되고 있으니 아래와 같이 재귀로 풀면 될 것 같습니다. 

 

1번째 -> 1

2번째 -> 12

3번째 -> 121

4번째 -> 1213

5번째 -> 12131

6번째 -> 121312

7번째 -> 1213121

 

그런데 3까지 붙여봐도 만족하는 숫자가 나오지 않을 때가 문제입니다. 8번째 경우가 그러합니다.

 

8번째 -> 12131211 -> x

          -> 12131212 -> x

          -> 12131213 -> x

이 경우엔 1, 2, 3이 만족하지 않음으로, 7번째(1213121)부터 다시 수정해야합니다.

7번째 -> 1213123

8번째 -> 12131231

 

7번째까지 만들어서 8번째로 넘긴 후 다시 7번째로 돌아와야합니다. 이걸 어떻게 재귀식으로 표현할까요?

 

이 문제는 다시 보면 그래프 탐색 중 깊이우선탐색 문제와 유사합니다.

일단 탐색해서 내려가보다가, 아니면 다시 올라오는 겁니다. 

코드로 살펴보겠습니다.

public String barCode(String str, int len) {
    String chr = "123";
    //2. 원하는 길이가 나오면 중단
    if(str.length() == len) return str;

    for(int i = 0; i < chr.length(); i++) {
        String currentStr = str + chr.charAt(i);
        if(isValid(currentStr)) {
            //1. 하나씩 붙이면서 다음으로 넘겨주다가
            String founded = aux(currentStr, len);
            //4. null을 반환받으면, 계속 탐색.
            if(founded != null) return founded;
        }
    }
    //3.하나씩 붙이다가 셋 다 조건을 만족하지 못하면 null반환
    return null;
}

 

 

 

우선 위의 예시에서 currentStr로 문자열을 합치고 유효성 검사를 통과한 currentStr을 다시 재귀 메서드의 인자로 넘겨주는 행위가 더 깊은 depth로 내려가는 행위라고 이해한다면, 

 

재귀 메서드를 호출하는 것을 멈추고 어떤 값을 리턴하는 행위가 얕은 depth로 올라가는 행위라고 이해할 수 있습니다.

위의 예시에서는

 

if(str.length() == len) return str;

String founded = aux(currentStr, len); 부분과

 

밑의 return null부분입니다.

 

첫 부분은 원하는 값을 찾았을 때, 한 depth씩 위로 찾은 값을 전달하고 있습니다. 즉 null이 아닌 값을 리턴하면, 최종 값으로 리턴됩니다.

 

반면, null을 리턴하면, 딱 한 depth만 위로 올라갑니다. 그리고 남은 for문을 계속 돌게 되죠.

만약 또 null을 리턴하게 된다면, 또 한 depth 올라가게되고, 원하는 값을 찾았다면 또 아래로 내려가게 됩니다.

그림으로 보면 아래와 같습니다. 

 

결국 해당 depth를 모두 돌아도 원하는 값을 못찾는다면 null을 리턴하고, if문을 통해서 리턴 값이 null인지 아닌지 검사하여 null이 아닐 경우(즉 원하는 값을 찾았을 경우) 그 값을 리턴 하는 로직이 핵심이었습니다.

이 로직을 통해 직전 depth로 올라갈 수 있다는 것을 알 수 있습니다.