백트래킹 (Backtracking)

백트래킹(Backtracking)

 

알고리즘을 어느 정도 공부하게 되면 백트래킹이라는 용어를 많이 들어봤을 것이다.

가끔 백트래킹이랑 완전 탐색을 같은 용어로 사용하게 되는데 오늘 확실히 정리해서 이해하도록 하자.

 

많은 블로그들을 검색하면서 공부했지만 이게 가장 나에게는 이해가 되는 정의였다.

 

해를 찾는 도중 다음의 경우가 해가 아니라면 되돌아가서 다시 해를 구하는 기법

 

무슨 말이냐면 분명 이 길로 가면 막히는 곳이 나오는데?라고 생각되면 다른 곳으로 방향을 트는 것이다.

이미 그 길은 내가 끝까지 가보지 않더라도 막힌 길을 알기 때문이다.

 

DFS 기법으로 하게 되면 막힌 곳을 알더라도 끝까지 가서 확인한다.  -무식한 방법-

백트래킹 기법으로 하게 되면 "아 이 길은 막힌 곳이니까 다른 곳으로 가자." -현명한 방법-

 

백트래킹에 사용되는 용어들

 

유망하다(promising) : 해가 될 가능성이 존재하는 루트

가지치기(pruning) : 배제하다. 유망하지 않다.

 

막힌 곳인 걸 알면 그 길은 배제하고 나머지 가능한 길만 생각한다는 것.

현재 위치에서 다음 위치에 대해서 유망한 지 검사하기.

 

테크닉, 상상해보자.

현재 돌에서 a, b, c, d 돌로 넘어가야 한다.

내가 현재 돌에서 a로 일단 이동해본다.

a로 왔는데 규칙에 어긋나지 않다면?(유망하다면) 다음 단계로 진행하고,

아니라면 현재 돌에서 a를 배제한 나머지 돌에서 다시 이동을 시도해본다.

 

또 다른 방법은

일단 두고 시작한다.

바둑 판을 상상해보면 일단 바둑알을 바둑 판에 두고 경기를 끝내기(하나의 경우의 수)

다시 돌아와서 바둑 판에 뒀던 바둑알을 무르고 다시 다른 곳에 두는 것이다.

돌아올 때는 반드시 내가 방문했던 곳을 지워야 한다. (복원하기)

어찌 보면 유망하기보다는 완전 탐색에 가깝다고 생각된다.. 써보고 보니까

 

+(추가)

아래와 같이 이런 류의 기법들은 흔히 완전 탐색이지만,

중간에 가지치기를 하는 것이 있다면 백트래킹이라고 생각하면 된다.

백트래킹은 그냥 완탐 처럼 보이지만 중간에 자를 수 있거나 배제할 수 있다면 이것 또한 백트래킹이기 때문이다.

// 흔히 보는 완탐
vis[i] = true;
dfs(cnt + 1);
vis[i] = false;

// 하지만? 이렇다면 백트래킹
if(promising() == false) continue;

정리

 

한마디로 모든 경우의 수를 보는 완전 탐색과 비슷하지만, 조건을 만족할 때(유망할 때)만 확인한다는 점에서 다르다.

 

대표적인 문제는  N-Queen