백트랙킹
- ‘되추적’이라는 뜻
- 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법
- 모든 경우의 수를 찾아보지만 그 중에서도 가능성있는 경우의 수만 찾아보는 방법
브루트포스, DFS와 차이점
- 브루트포스
- 말 그대로 모든 경우의 수를 찾아보는 것
- 장점 : 모든 경우의 수를 탐색하기 때문에 만족하는 값을 100% 찾아낼 수 있다.
- 단점 : 모든 경우의 수를 탐색하기 때문에 경우의 수가 많으면 자원을 많이 필요로 한다.
- 백트래킹
- 해당 노드의 유망성 판단 = 해당 범위 내에서 조건을 추가하여 값의 유망성을 판단한다.
- 장점 : 탐색하는데 필요한 자원을 줄일 수 있다.
- DFS 깊이우선탐색
- 트리순회의 한 형태. 백트래킹에 사용하는 대표적인 탐색 알고리즘
- 백트래킹 방법 중 하나가 DFS
- 깊이를 우선으로 먼저 탐색하는 방법
백트래킹 대표 예제 - 순열 Permutation 구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;
public class Permutation {
public static void main(String[] args) {
List<String> arr = new ArrayList<>();
arr.add("a");
arr.add("b");
arr.add("c");
int r = 2; // 뽑을 개수
String[] result = new String[r];
permutation(arr, result, 0, arr.size(), r);
}
/**
* 순열 구하기
* @param arr : 입력 리스트
* @param result : 결과 리스트
* @param depth : 배열을 채워 넣을 순서 (ex. result[depth])
* @param n : 전체 개수
* @param r : 뽑을 개수
*/
private static void permutation(List<String> arr, String[] result, int depth, int n, int r) {
if (depth == r) {
System.out.println(Arrays.toString(result));
return;
}
for (int i = 0; i < n - depth; i++) {
// arr.remove(i)는 삭제되는 arr의 인덱스 i번째 값을 반환한다.
result[depth] = arr.remove(i);
// 재귀호출 depth를 1 늘려 result의 다음 인덱스 값을 구한다.
permutation(arr, result, depth + 1, n, r);
// 다시 원본 배열에 지웠던 값을 넣는다.
arr.add(i, result[depth]);
}
}
}
DFS 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
boolean[] visit = new boolean[N];
int[] arr = new int[M];
public static void dfs(int N, int M, int depth) {
//재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
if (depth == M) {
for (int val : arr) {
System.out.println(val + " ");
}
System.out.println();
return;
}
for (int i = 0; i < N; i++) {
//만약 해당 노드를 방문하지 않았다면
if (visit[i] == false) {
//해당 노드를 방문 상태로 변경
visit[i] = true;
//해당 깊이를 index로 하여 i+1값 저장
arr[depth] = i + 1;
//다음 자식 노드 방문을 위해 depth를 1씩 증가시키면서 재귀 호출
dfs(N, M, depth + 1);
//자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
visit[i] = false;
}
}
return;
}
