[알고리즘] 백트래킹 (Back-tracking)

백트래킹?

트리방식으로 동작된다고 이해하면 쉽다.

재귀함수를 통해 for문을 돌려 깊이를 마음대로 설정할 수 있음.

 

DFS랑 백트래킹 뭐가 달라?

재귀함수를 통한 dfs랑 백트래킹이 유사하지 않나?라는 생각이 들었다.

둘 다 탐색이지만 원하는 값을 찾기 위한 방법에서 차이가 발생한다.

 

백트래킹은 불필요한 탐색을 하지 않는다.

경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로에 왔다면 더 가지 않고 되돌아온다.

 

아래 사진을 보면 느낌이 팍 올 것이다.

되돌아올 때 밑에 노드는 애초 방문하지 않은 것처럼.

dfs의 방문처리는 보통 배열을 사용하여 인덱스를 활용한 방문처리를 한다.

하지만 백트래킹은 다시 부모노드로 올라갈 때 이전의 노드들을 방문했다고 생각하지도 않고 진행한다.

그래서 보통 append() pop()을 통해 경로를 만든다.

 

마무리

일단 인터넷과 사람들에게 물어보며 간단히 정리해 봤는데

한마디로 완전 탐색을 하는 코드에 조건을 붙여 가지치기를 하고 방문처리의 방법을 다르게 한다? 

이 정도로 이해했다.

 

더 dfs 백트래킹 문제들을 풀어보며 몸으로 감으로 익히는 게 중요해 보인다.

문제 풀러 가겠다.