백트래킹 코드 정리

정말 재귀함수를 이용한 탐색은 너무도 어려운 것 같다.

이해는 해도 코드를 짜기가 정말 어려운 것 같아서 이번엔 백트래킹을 확실히 익히고자 

포스팅을 진행하겠다.

백트래킹 : 탐색을 진행할 때 가지치기를 하는데, 단말노드까지 가기 전에, 확 꺾어버려서 

다음 단말 노드로 이동하는 것. 

(진행하고 있던 방향이 틀어지는 것임)

이 말을 잘 기억해야한다. 

"진행하고 있던 방향이 틀어지는 것"

처음에는 단순히 "뒤로만 가면 되지 뭐.. " 라는 생각이었으나, 하나의 노드가 쭉쭉 내려오다가 

중간에서 꺾이게 되면 이 전에 쭉쭉 내려오던 과정이 사라지기 때문에 , 단순히 뒤로만 가는 것이 아니라,

한 과정 전체가 뒤로간다고 생각해야 한다.

---

[코드]

public class BackTracking_예제 {

private static int[] input = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

private static int cnt = 0;

private static StringBuffer sb;

public static void main(String[] args) {

// TODO Auto-generated method stub

sb = new StringBuffer();

int k = 10;

for (int i = 0; i < k; i++) {

cnt = 1;

dfs(i, input[i] + " "); // 기준이 되는 자릿수를 변경해주는 것

}

sb.append("\n");

System.out.println(sb.toString());

}

private static void dfs(int v, String str) {

System.out.println(str + "/" + cnt);

if (cnt == 7) {

sb.append(str + "\n");

} else {

for (int i = v + 1; i < 10; i++) {

//System.out.println("cnt : " + cnt + " / " + " i : " + i);

++cnt;

dfs(i, str + input[i] + " ");

/* System.out.println("v값 : " + v);

System.out.print("다시 돌아갔을 때의 i : " + i);*/

}

}

--cnt;

return;

}

}

---