백트래킹(Backtracking)

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

Backtracking이란?

Backtracking(백 트래킹)은 해답을 구할 수 없는 경우가 나온 경우, 더 진행하는 것을 포기하고 이전 상태로 되돌아가서 다른 경우를 찾는 방법을 말합니다. 흔히 생각할 수 있는 예시가 '미로 찾기'입니다. 미로를 빠져나가는 방법들 중에서 가장 많이 알려진 방법이 '우수법' 입니다. 오른손으로 한쪽 벽을 짚으면서 걸으면 무조건 미로를 빠져나갈 수 있는 방법입니다.

https://youtu.be/YS4ng_vKr7o?t=89 

우수법으로 나아가는 과정이 백트래킹과 같다고 생각이 됩니다.

간단한 미로

위와 같은 미로가 있다고 합시다. 파란 점의 위치에서 우수법으로 미로를 해결하면 먼저 위쪽으로 향할 것입니다. 그러면 길이 막혀있을 것이고 다시 이전 위치로 돌아와 아래로 나아가게 됩니다. 이러한 과정이 백 트래킹입니다. 해답을 구할 수 없는 경우가 나와서 이전의 상태로 돌아가 다른 경우를 탐색하는 과정이 우수법으로 미로를 빠져나가는 과정과 같습니다.

State-Space Tree

State-Space Tree(상태 공간 트리)는 모든 답의 후보들을 저장하고 있는 트리입니다. 미로 찾기 문제로 트리를 만들 경우, 각 노드는 갈림길의 위치라 할 수 있습니다. 이 트리의 루트 노드부터 리프 노드까지 각 노드의 내용들이 미로를 빠져나가는 경로가 됩니다.

source: https://dad-rock.tistory.com/691

S가 출발, T가 도착이라고 할 때 이러한 방식으로 상태 공간 트리가 그려질 것입니다. S에서 탐색을 시작해서 노드 하나씩 방문해서 이 노드 이후로 해를 구할 수 있는지 없는지 판별하고 다음 노드로 탐색을 진행하면 시작 지점에서 도착 지점까지의 미로 경로를 얻게 됩니다. 이렇게 상태 공간 트리를 그려놓고 탐색을 하는 과정은 DFS와 동일합니다.

 

상태 공간 트리에서 각 노드를 두 가지로 나눌 수 있습니다.

• Promising: 이 노드 이후로 해답이 있을 가능성이 있는 노드
• Non-promising: 이 노드 이후로는 해답이 없는 노드

따라서 백 트래킹 과정을 아래와 같이 다시 설명할 수 있습니다.

백 트래킹은 상태 공간 트리를 탐색해 나가는 과정이며 각 노드마다 promising인지 non-promising인지 판별합니다. Non-promising 노드인 경우 이 노드의 부모 노드로 돌아가 다른 노드를 탐색하고, promising인 노드이면 이 이후로 계속 탐색을 이어갑니다.

 

하지만 실제로 구현할 때는 이 상태 공간 트리를 만들지 않습니다. 상태 공간 트리는 문제를 풀어나가는 방법을 생각하기 위해 존재하는 것이지 트리 구조체(또는 클래스)를 만들지 않습니다. Backtracking으로 문제를 풀 때는 현재 상태에서 나올 수 있는 경우의 수만큼 재귀적으로 함수를 호출해 문제를 해결합니다.