백트래킹

Backtracking.

1 알고리즘에서의 백트래킹

모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. 생각은 다른 알고리즘보단망할 다이나믹 프로그래밍이라든가안해도 되는데 구현(코딩)이 어렵다.

DFS는 상태공간을 나타낸 트리에서 바닥에 도달할 때까지 한 쪽 방향으로만 내려가는 방식이다. 미로찾기를 생각하면 쉽다. 한 방향으로 들어갔다가 막다른 길에 다다르면(=트리의 바닥에 도착) 왔던 길을 돌아가서 다른 방향으로 간다. 이 짓을 목표지점(=원하는 해)이 나올 때까지 반복한다.

간단한 경우 구현을 재귀함수로 할 수 있으며, 재귀함수를 쓰기 힘들면 스택을 써서 할 수도 있다. 대다수의 문제들은 DFS를 써도 무방한 경우가 많다. 그러나 DFS를 절대 쓰면 안되는 경우가 있는데, 트리의 깊이가 무한대가 될 때이다. 미로찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 탈출할 수 없게 된다. (물론 중복검사를 막기 위한 장치를 넣을 수도 있지만, 이꼴나는 경우엔 그냥 BFS 쓰는게 낫다) 또 분기점 없이 길이만 죽어라 긴 길이 나타나면 스택 오버플로우가 발생할 수 있다.

간단한 방식인데 잘 안쓰는 편이 낫다. BFS에 비해서 DFS는 속도가 매우 느리다. 위의 미로찾기도 4방향(또는 8방향)중 마지막으로 진입하는 방향으로만 갔을 때 도착점이 있다거나 최단거리를 구하라고 한다면 답이 없다. 이는 경우에 따라 다르다. DFS가 최적일 때가 있고, BFS가 최적일 때가 있다. 예를 들어, 어차피 모든 경우의 수를 고려해야 하는 문제라면(nQueen의 일반적인 해), DFS를 사용하는것이 더 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가(..). 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS, 최단거리 구하기에서는 BFS를 사용하는게 편리하다고 할 수 있다. 물론 이것도 에외가 있기 마련이다. 당신의 실력에 달렸다...

BFS는 모든 분기점을 다 검사하면서 진행하는 방식이다. 철수와 영희가 계단에서 가위바위보를 하며 뻘짓게임을 하고 있을 때, 철수가 원하는 지점에 갈 수 있는 최소 승리 횟수는 얼마인가? 같은 문제에서 효과를 발휘한다. 이 경우 DFS는 깊이가 무한인 경우에 빠져나오지 못하며, 중복 방지를 한다고 치더라도 올바른 해를 찾는데 시간이 많이 걸린다. BFS는 모든 분기를 다 검색하면서 상태공간을 탐색한다. 철수가 이겼을 때, 비겼을 때, 졌을 때를 검사하고, 그 경우마다 각각 또다른 3가지 가능성을 전부 검사한다. 이러다가 어느 한 부분에서 원하는 해를 발견하면, 이것이 최단 거리가 된다.

BFS는 큐를 써서 구현한다. 각 경우를 검사하면서 발생하는 새로운 경우를 큐에 집어넣고, 검사한 원소는 큐에서 뺀다. BFS의 장점은 DFS가 못건드리는 문제를 풀 수 있는 것이지만, 공간 복잡도가 지수 스케일로 폭발하기 때문에 가지치기를 제대로 안하면 DFS보다 빨리 오버플로우에 다다를 수 있다.

이 BFS에서 조금 더 발전한 방식이 Best First Search 방식이다. 큐 대신 우선순위 큐(보통은 힙으로 구현되는)를 써서 구현하는데, 발생하는 새로운 경우를 순차적으로 검사하는 Breadth First Search와는 달리 현재 가장 최적인 경우를 우선적으로 검사하므로 상대적으로 효율적이다.

백트래킹은 모든 경우를 다 고려하기 때문에 귀찮을때 이걸 쓰면 어지간해서는 해결할 수도 있다. 다이나믹 프로그래밍으로 할 수 있는 것도 다 구현할 수 있으니 시간과 메모리만 해결하면 매우 유용하다. (물론 최악의 경우 지수 시간 복잡도를 갖는다)

또한 무의미한 탐색을 막아줄 가지치기(Bounded(Promising) function)를 적용하여 적당한 지능(Heuristic)을 부여한다면 상당히 효과적인 해결방법이 될 수 있다. 아까 본 철수 영희 문제의 경우, 목적지점과 계속 반대로 가려는 가지는 굳이 탐색할 필요가 없으므로, 적절히 쳐내면 된다. 이렇게 하면 전혀 가망이 없는 경우로의 탐색이 이루어지지 않으므로 계산 성능이 향상된다.

백트래킹의 가지치기를 연습하고 싶다면

KOI에 나온 "공주님의 정원"이라는 문제가 있다. (미친듯이 커팅해야 답이 나온다.) (정해는 그리디 알고리즘)

2 게임에서의 백트래킹

일반적으로 특정 퀘스트나 스토리를 클리어하기 위해 게임을 진행한 뒤, 자동으로 초기 지점으로 돌아오는 기능 등이 없어 왔던 길을 플레이어가 직접 캐릭터를 조정해 처음부터 다시 돌아와야 되는 경우를 칭하는 말.

주로 RPG 요소가 있는 게임에서 적용되는데, 가장 대표적인 경우의 예시를 들자면 아래와 같다.

• 특정 NPC에게서 퀘스트를 받는다.
• 지정된 지역으로 이동해 퀘스트를 완료한다.
• 퀘스트를 부여해준 NPC에게 다시 돌아가 퀘스트를 정리하고 보상을 받는다.

이런 과정에서 가장 마지막에 해당되는 부분이 백트랙킹이라고 볼 수 있다. 현실성을 고려하자면 해당 작업을 완료한 뒤에 그것을 제시해준 의뢰인에게 돌아가 임무 완수를 확인 받아야 보상을 받는 것이 당연하다.

하지만 대부분의 게임에서 한 플레이어가 이렇게 플레이하게되는 퀘스트가 수십, 수백여개에 이른다는걸 고려하면 생각보다 상당히 짜증을 부르는 과정이다. 당연히 이미 퀘스트와 스토리에 관련된 것은 다 해결된 다음이기 때문에 플레이어에게 재미를 부여해줄 만한 부분이 거의 없어진 상태이니 그냥 의미 없이 시간만 소모하게 되는 과정이기 때문이다. 해당 게임이 패스트 트래블, 빠른 여행 기능이 없는 게임일 경우 이 스트레스는 몇 배로 더 강해진다. 거기다 스토리와는 관련이 없는 반복 퀘스트의 비중이 높을 수 밖에 없는 온라인 게임들의 경우는 그 짜증이 훨씬 더 심할 수 밖에 없다.

세심한 개발사의 경우 반복 퀘스트들의 경우 굳이 해당 NPC에게 돌아가지 않아도 퀘스트 창을 열어 클릭만 해도 임무를 완료할 수 있다거나, 퀘스트 완료와 동시에 플레이어 캐릭터를 그 NPC의 앞으로 빠른 이동시키는 등의 간편한 기능을 게임에 넣어두는 경우도 볼 수 있다. 그러나 많은 수의 제작사들이 플레이 타임을 좀 더 늘리기 위해서라도 굳이 이런 조치까지 취하지는 않는 경우가 많아 플레이어들에게 지탄을 꽤 많이 받는 편. 그럼에도 불구하고 게임 개발 기술이 과거와는 비교도 안될 정도로 향상된 2010년도에 이르러서도 백트래킹은 여전히 줄어들 기미가 보이지 않는다.

다만 오픈 월드 식의 샌드박스 게임의 경우, 대부분 방대한 게임의 필드를 직접 돌아다녀야 랜덤 인카운터나 새로운 지역 발견 등을 포함한 그 게임의 진정한 컨텐츠를 즐길 수 있는 경우가 많기 때문에 일부러 백트래킹을 조장하는 경향이 있다. 이런 게임들을 무조건 빠른 이동으로 주어지는 퀘스트만 후다닥 해결하며 플레이해서는 내재된 방대한 컨텐츠를 거의 건드려보지 못하기 때문에 진정한 재미를 못느끼게되는 경우가 많기 때문.