👑 백트랙킹 개념
: 현재 상태에서 가능한 경로들을 모두 탐색하다가, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아간다. 즉, 왔던 길을 되짚어가는 Backtrack을 한다!!
-> 트리구조: 해당 자식 노드가 조건에 맞지 않으면, 부모 노드로 다시 돌아간다.
-> 보통 재귀를 통해 구현! 재귀 함수가 호출되고 조건에 맞지 않으면 종료되고 그 전에 호출된 재귀로 돌아옴
👑 DFS와의 차이점
-> 둘 다 원하는 값을 찾기위한 탐색 알고리즘
- 백트랙킹: 불필요한 탐색을 하지 않는다.
- DFS: 모든 경우의 수를 탐색한다.
ex> a = [132, 234, 123] 이라는 배열이 있다. 123이라는 값을 찾고 있다고 할 때 백트랙킹과 DFS에서 차이를 보인다. 첫번째 요소인 132와 비교를 한다고 해보자.
- 백트랙킹: 백의 자리 비교 후, 같으므로 십의 자리를 비교한다. 하지만 같지 않으므로, 다음 단계로 넘어가서 234와 비교하게 된다.
- DFS: 모든 경우의 수를 탐색한다. 십의 자리 3이 원하는 수가 아님에도, 일의 자리 수까지 모두 탐색한다. 즉, 트리의 바닥에 도달할 때까지 탐색은 계속된다.
👑 백트랙킹 문제 예시 - N과 M
https://www.acmicpc.net/problem/15649 -> 총 n개의 숫자로 요소 m개 짜리 수열을 출력하는 문제
-> 하나씩 요소를 추가하면서,
i=1, s = [1] -> [1, 2] -> [1] -> [1, 3]
i=2, s = [2] -> [2, 1] -> [2] -> [2, 3]
i=3, s = [3] -> [3, 1] -> [3] -> [3, 2]
와 같이 동작한다.
👑 파이썬 구현
-> ans에는 요소들을 추가한다. 그래서, 그 배열의 길이와 m이 같은 경우에는 return 하도록 하였다.
i=1: 1을 먼저 넣는다. 그 후, back()을 통해, 1부터 다시 검사하면서 없는 값을 넣는다. 길이가 같아지면 출력을 하고, 마지막 숫자를 pop한다. 그렇다면, 마지막에 대한 재귀는 끝나고, for문에서 그 전 단계의 i를 증가시켜 마지막 요소에 또 넣는다. 배열의 길이 만족하므로 출력한다. 그 다음 pop을 한다. 그런데, 마지막 재귀에 대한 i가 4로 범위를 벗어났으므로 그 재귀는 끝난다. 따라서 pop을 통해 2번째 요소를 꺼낸다. 그 단계의 재귀로 돌아가서 i는 하나커지며, i=3이 된다. back을 통해 다시 검사하며 마지막 요소 4를 넣어준다. 또, 길이가 같아졌으므로 출력 후, 마지막 요소를 pop한다. 이런식으로......두번째 요소가 pop이었는데 마지막 요소까지 모두 pop을 했다고 하자면. 두번째 재귀에서도 for문을 벗어난다면, 다시 pop을 하고, 첫 번째 호출에서의 i값으로 돌아가 첫번째 요소가 2로 바뀐다.
⭕ 나의 언어로 정리하자면 이렇다...... 반복문 재귀호출 부분이 이해가 되지 않았다. 그냥 마지막 재귀가 끝나면, pop하고, 그 전 단계 재귀의 i가 1증가한다고 생각하자!!
--> 즉, 최근의 재귀가 끝나면, 다음 i로 넘어간다!!
