🔎 백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법 → 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다 == 가지치기 (가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다!) 백트래킹 기법의 유망성 판단 어떤 값이(어떤 노드가) 해가 될 가능성이 있다면 유망하다고 하며, 유망하지 않은 값에 가지 않는 것을 가지치기라고 한다. 유망하지 않다고 판단되면 그 값의 이전으로 돌아가 다음 값으로 넘어간다. (이전 노드로 돌아가 다음 자식 노드로 간다.) 🔎 DFS vs 백트래킹 vs 분기한정법 DFS 가능한 모든 경로를 깊이 우선으로 탐색하는 것 (한 방향으로 갈 수 있는 경로를 먼저 탐색) → 현재 정점과 인접한 간선들을 모두 검사하여 아직 ..
