알고리즘 백트래킹(backtracking)

백트래킹 :

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는 알고리즘이다. 

 

현재 노드가 조건을 만족하는지 확인 -> 만족한다면 자식노드로 가서 조건 만족하는지 확인 -> 자식노드가 만족하지 않으면 다른 자식노드 확인 -> 모든 자식노드가 조건 만족하지 않으면 다시 부모노드로 돌아간다. 

 

참고한 블로그

chanhuiseok.github.io/posts/algo-23/