dfs

안녕하세요 오늘은 백트래킹에 대한 포스팅을 작성해보겠습니다. 목차 1. 백트래킹 기법 2. DFS와의 차이점 3. 대표적 문제예시 4. N-Queen 코드 한 줄 요약 백트래킹은 모든 후보 검사가 아니다, 즉 완전탐색이 아니다. 1. 백트래킹 기법 어떤 노드의 유망성을 점검한 후 에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다. 가지치기(pruning): 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다. 2. 백트래킹과 DFS와의 차이 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써, 시도 횟수를 줄인다. 깊이 우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단할 수 있다. N! 가지의 경우..