mun dev

백트래킹이란? 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다고 한다. DFS와 백트래킹 DFS(Depth First Search) 깊이 우선 탐색은 가능한 모든 경로를 탐색한다. 불필요할 거 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 최적으로 줄이지 못한다 . 따라서 N!의 경우의 수를 가지는 문제는 DFS로 처리하지 못할 가능성이 크다. 백트래킹 백트래킹은 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다. 이를 가지 치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 DFS보다 ..