참고
백트래킹
NOTE
탐색도중 지금의 경로가 답이 되지 않을 것 같다면, 이전 단계로 다시 돌아가는 방식! (가지치기)
DFS & BFS가 전체탐색이라면, 백트래킹은 조건에 맞는 노드로만 탐색한다.
•
백트래킹 - 순열/조합
NOTE
static void dfs(int step){
// 길이가 2가 된다면
if(step == 2){
for (Integer i : list) {
System.out.print(i);
}
System.out.println();
// 이전에는 그냥 값넣어준다.
}else{
for (int i = 0; i < numbers.length; i++) {
list.add(numbers[i]);
dfs(step+1);
list.remove(step);
}
}
}
Java
복사
순열생성
step이라는 깊이 제한을 두고, 이전 상태로 돌린다.
// 값은 정렬되어서 들어온다고 가정한다
// 사용한 index값 다음부터 사용함
static void dfs(int t, int step){
if(step == 2){
for (Integer i : list) {
System.out.print(i);
}
System.out.println();
}
else{
for (int i = t; i < numbers.length; i++) {
if(!visited[i]){
visited[i] = true;
list.add(numbers[i]);
dfs(i+1,step+1);
list.remove(step);
visited[i] = false;
}
}
}
}
Java
복사
조합생성
step이라는 깊이 제한을 두고, 이전 상태로 돌린다.
private var dy = Array<IntArray>(n+1){IntArray(n+1)}
private fun dfs(n:Int, m: Int): Int {
// 메모제이션을 이용해서 이미 수가 차있다면 그대로 사용
if (dy[n][m]>0) return dy[n][m]
// nC0=1, nCn=1이기 때문에 종료 조건
return if (m==0 || n==m) 1
else {
// 메모제이션 이용
dy[n][m]= dfs(n-1,m-1)+dfs(n-1,m)
dy[n][m]
}
}
Kotlin
복사
nCr = n-1Cr-1 + n-1Cr
5C3을 구하는 코드
백트래킹 - N Queen
NOTE
N-Quuen에서 유망하지 않은 노드는 탐색하지 않는다.