DFS / 백트래킹

DFS / 백트래킹 이 두가지가 항상 함께 등장하는데, 어떤 차이가 있는지 몰라 정리해보았다.

 

쉽게 이야기 하자면 끝까지 가는지(DFS)/ 돌아오는지(백트래킹) 의 차이이다. 

그래서, DFS 탐색하며 조건을 확인하며 해당 노드가 유망하지 않으면 탐색하지 않는 것 = 백트래킹 이다.

 

백트래킹도 일반적으로 재귀 형태로 작성되며 크게 3개의 내용을 작성한다.

• 재귀를 진행하는 동안 사용될 깊이(depth)를 매개변수로 넣기
• 재귀가 종료될 때 수행할 내용
  • 재귀 종료조건 = 보통 정해진 depth에 도달했을 때
  • dfs 함수의 제일 앞에서 종료 조건에 포함되었는지 먼저 검사한다.
• 재귀가 진행 중이면 가지치기(백트래킹)할 내용

 

백트래킹으로 조합하는 함수를 구현하면 아래와 같다. 

public static void combination(int[] arr, int[] result, int start, int depth) {
    if (depth == result.length) {
        // 조합 출력
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
        return;
    }

    for (int i = start; i < arr.length; i++) {
        result[depth] = arr[i];
        combination(arr, result, i + 1, depth + 1);
    }
}

// 아래와 같이 사용할 수 있다. 
int[] arr = {1, 2, 3, 4};
int[] result = new int[2];
combination(arr, result, 0, 0);

// 출력 결과
1 2
1 3
1 4
2 3
2 4
3 4

 

 

사용되는 변수

- arr: 원본 배열
- result: 조합을 저장하는 배열, 배열의 크기가 nCr 중 r이 된다. 
- start: 조합을 만들 때 시작할 인덱스
- depth: 현재 조합의 깊이

 

재귀 함수의 작동 방식

 

1. depth가 result.length과 같으면 (모든 숫자가 선택된 경우):
- 조합 출력
- 재귀 함수 종료

 

2. depth가 result.length보다 작으면:
- start 인덱스부터 arr.length까지 각 숫자를 순회
- 숫자를 선택하고 result 배열에 저장
- depth를 1 증가시키고 재귀 함수 호출

 

그렇다면 위 코드에서 백트래킹이 적용되는 부분이 무엇인가? 

- combination 함수는 재귀 함수를 사용하여 모든 경우의 수를 탐색
- depth가 result.length보다 작을 때, start 인덱스부터 arr.length까지 각 숫자를 순회하며 모든 경우의 수를 탐색
- 조건에 맞지 않는 경우 (예: depth가 result.length보다 크거나, 이미 선택된 숫자를 선택하려는 경우) 다시 돌아가 다른 선택을 시도

=> 즉, dfs 탐색할 때 조건을 확인하여 유효하지 않으면 탐색하지 않음 = 백트래킹 이 적용됨. 으로 볼 수 있다. 

 

만약, DFS 탐색 시에 백트래킹을 적용하지 않았다면, start 인덱스 필요없이 for(int i =0; i< size; i++) 같은 형식을 모든 값들을 탐색하기에 값이 중복되어서 나올 것이다. => {1,2} , {2,1} 둘 다 탐색

 

좀 더 자세히, 함수가 어떻게 재귀적으로 호출하는지 그림을 그려보았다.

즉, 인덱스 순서대로 DFS 탐색하며 조건이 되지 않으면 탐색하지 않는다. (=백트래킹)

 

- 또, 보니까 BFS와 비슷하다는 생각을 했는데 (당연히 탐색이니까,,, ) 일단 차이점으로 생각되는 것은 

1. BFS는 큐로 구현해서 q.isEmpty == true가 되었을 때 탐색이 끝난다.

2. DFS는 재귀함수로 구현해서 정해진 depth에 도달했을 때 탐색이 끝난다. 

 

 

 

 

---

참고

https://velog.io/@newon-seoul/%EB%AC%B8%EA%B3%BC%EC%83%9D%EC%9D%B4-%EC%A0%81%EC%96%B4%EB%B3%B4%EB%8A%94-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-%EC%9E%AC%EA%B7%80%EC%99%80-DFS-%EB%A5%BC-%EA%B3%81%EB%93%A4%EC%9D%B8

문과생이 적어보는 백트래킹 (재귀와 DFS 를 곁들인)