Dot Algo∙ DS/알고리즘 개념
2021. 5. 12.
[알고리즘] 백트래킹(Backtracking) 가지치기 기법 (Java)
백트래킹 Backtracking 백트래킹은 조건 만족 문제(CSP; Constrain Satisfication Problems)를 해결하기 위해 사용하는 알고리즘이다. 이는 어떤 조합을 탐색하는데 무작정 그리디하게 모든 곳을 탐색하는 것이 아니라 조건에 만족하지 않으면 왔던 길을 되돌아가 조건이 만족하는 부분에 한해 완전 탐색하는 것이다. ❐ 백트래킹의 대략적인 흐름은 다음과 같다. 1. 어떤 노드의 유망성(탐색 가능성) 체크 1-1. 탐색 가능하면 그대로 탐색 1-2. 탐색이 가능하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자식노드를 탐색 BACK! - ✂️가지치기 그래서 백트래킹(되추적)이라고 불리는 것이다. DFS + 백트래킹? DFS는 모든 노드를 방문하고자 하는 경우에 주로 사용한다. D..
![[알고리즘] 백트래킹(Backtracking) 가지치기 기법 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/FznlW/btq4K19kxDr/dR0QjltR8dFLjCue2aXPlK/img.jpg)