[알고리즘] 되추적(Backtracking)을 알아보자.

오늘의 주제는 되추적(Backtracking) 이다. 

저번 포스팅인 깊이우선탐색(Depth-First Search)과 넓이우선탐색(Breath-First Search)의 몸풀기를 거치고

최단경로(Shortest Path) 알고리즘에 들어가는 첫 걸음이라고 생각하고 가벼운 마음으로 읽어보면 되겠다.

우선 되추적(Backtracking)이 뭔지부터 알아보자.

『 퇴각검색(영어: backtracking, 한글: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. 

"퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다.

문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 

한정 조건을 구성하려면 각각의 변수들은 값이 있어야 한다. 퇴각검색은 모든 조합을 시도해서 문제의 해를 찾는다. 

이것이 장점이 될 수 있는 이유는 퇴각검색 구현 방법들이 많은 부분 조합들을 배제하기 때문이다. 결국 풀이 시간이 단축된다. 』

라고 위키백과에 써있다..... 뭔소리지... -_-;

어쨌든 우리가 알아야 하는것은 "배제", "풀이 시간이 단축된다" 이다. 

쫌더 이해에 도움이 되는 다른글을 보면 

『 어떤 노드의 유망성 점검후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색. 』이다.

이 두 글의 설명을 정리해보면 유망하지 않으면 배제를 하고 부모노드로 되돌아가면서 풀이 시간이 단축된다. 이다.

글만 봐서는 유망하다는게 뭐고 왜 풀이시간이 단축되는지 이해하기 힘들어서 예를 들어보았다.

그리고 이 예를 통해서 되추적의 가장 중요한 개념인 유망하다를 알아볼것이다.

가장 쉽게 접할수 있는 예시로 4-Queens Problem 이다. 

4-Queens Problem은 4개의 Queen을 서로 상대방을 위협하지 않도록 4 * 4 체스판에 위치시키는 문제이다.

예를 들면 다음과 같다.

좌측최상단이 (1,1)이다.

그리고 이러한 문제를 트리로 표현해 보자면 다음과 같다.

이 문제는 앞에서 배운 깊이우선탐색(Stack)과 넓이우선탐색(Queue)을 사용하면 해결할 수 있다.!

되추적은 깊이우선탐색(Depth-First Search)과 마찬가지로 스택을 사용한다!

그렇다면 이를 천천히 풀어보자!

문제 : 4개의 Queen을 서로 상대방을 위협하지 않도록 4 * 4 체스판에 위치시키는 위치를 찾자!

방법 : 

Step1. 첫번째 행에서의 Queen의 위치를 선택하자!

이 상황에서 깊이우선탐색은 (1,1)노드의 자식인 (2,1),(2,2),(2,3),(2,4)를 스택에 넣을것이다.

하지만!! 되추적은 (2,1), (2,2)를 스택에 넣지 않는다!!

그 이유는 유망하지 않기 때문이다!!

이 처럼 되추적은 스택에 자식노드를 넣기전에 유망한지 즉 해답이 될 가능성이 있는지 확인한뒤 스택에 넣는다. 
그리고 (2,1), (2,2)는 해답이 될 가능성이 전혀 없기때문에( 체스의 Queen의 특성상 그 위치에 놓으면 죽는다. ) 아예 가능성에서 배제한다.

이를 스택과 그림으로 표현하자면 다음과 같다.

Step2. 스택을 꺼내서 (2,3)에 Queen을 넣어보자.

스택에서 꺼낸 (2,3)에 Queen을 넣은후 유망한 노드를 검사해보면 다음과 같다.

아무것도 없다!! 즉 3행에 Queen을 놓을수 있는 곳이 없다!

이를 스택과 그림으로 표현하면 다음과 같다. 

Step3. 또다시 스택에서 꺼내서 (2,4)에 Queen을 넣어보자.

※ (2,3)의 경우 유망한 자식이 하나도 없기때문에 더이상 유망하지 않다고 표현했다.

 

Step4. 또다시 스택에서 꺼내서 (3,2)에 Queen을 넣어보자.

다음 유망한 자식이 없다!!

더이상 밑으로 갈 길이 없다!! 그렇다면 Step3. 에서와 마찬가지로 부모로 돌아가서 다음 유망한 자식한테 간다!

그리고 (1,1)에 Queen을 놨을때 해답이 없기 때문에 (1,1)은 유망하지 않다는 결론이 난다.

Step5. 다음 유망한 자식인 (1,2)에 Queen을 놔보자.

...

이렇게 반복하다보면 다음과 같은 결과가 나온다.

이처럼 되추적은 해답을 찾는 과정에서 유망한지 즉, 해답이 될 가능성이 있는지!를 확인하고 유망하지 않다면

더이상 깊게 들어가지 않고 부모 노드로 돌아오는 방식을 취한다.

그리고 이러한 방식은 단순 깊이우선탐색을 했을때보다 엄청나게 효율이 증가한다.

단순 깊이우선탐색을 했을경우 검색해야 하는 노드의 갯수는

1개(Root) + 4개(1행) + 16개(2행) + 64개(3행) + 256개(4행) 중에

155번째 노드검색을 하다 해답(2-4-1-3)을 발견하게 되지만!

되추적을 사용할경우 27번의 노드검색만을 통해서 해답을 찾게된다!!

어찌보면 당연히 해야하는 검사를 통해서 단순 깊이우선탐색보다 효율을 몇배나 끌어올릴수 있게 되었다!

이제는 위에서 표현한 유망하지 않으면 배제를 하고 부모노드로 되돌아가면서 풀이 시간이 단축된다. 가 이해될것이다.

이 포스팅을 통해서 기억해야 할 것은 되추적은 『 스택을 사용하고 스택에 넣기전에 유망성검사를 한다.』 이다.

누군가에게는 작은도움이 되었기를 바라면서 오늘의 포스팅 끝~