백트래킹
Backtracking.
모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. 그냥 뇌없이 짤 수 있다는 것이 장점이다.
모든 경우의 수를 고려해야 하는 문제라면[1], DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가(...). 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은 DFS를 써도 일단 답은 나온다.
그러나 DFS를 절대 쓰면 안되는 경우가 있는데, 트리의 깊이가 무한대가 될 때이다. 미로찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 탈출할 수 없게 된다. 물론 중복검사를 막기 위한 장치를 넣을 수도 있지만, 그럴 바에는 BFS가 편하다. 또 분기점 없이 길이만 죽어라 긴 길이 나타나면 스택 오버플로우가 발생할 수 있다. 위의 미로찾기도 4방향(또는 8방향)중 마지막으로 진입하는 방향으로만 갔을 때 도착점이 있다거나 하면 DFS는 느리다. 그리고 최단거리 구하기에서는 BFS를 사용하는게 편리하다.
DFS는 상태공간을 나타낸 트리에서 바닥에 도달할 때까지 한 쪽 방향으로만 내려가는 방식이다. 미로찾기를 생각하면 쉽다. 한 방향으로 들어갔다가 막다른 길에 다다르면(=트리의 바닥에 도착) 왔던 길을 돌아가서 다른 방향으로 간다. 이 짓을 목표지점(=원하는 해)이 나올 때까지 반복한다.
재귀함수로 구현할 수 있으며, 재귀함수에 익숙하지 않다면 스택을 써서 할 수도 있다.
BFS는 모든 분기점을 다 검사하면서 진행하는 방식이다. 철수와 영희가 계단에서 가위바위보를 하며 게임을 하고 있을 때, 철수가 원하는 지점에 갈 수 있는 최소 승리 횟수는 얼마인가? 같은 문제에서 효과를 발휘한다. 이 경우 DFS는 깊이가 무한인 경우에 빠져나오지 못하며, 중복 방지를 한다고 치더라도 올바른 해를 찾는데 시간이 많이 걸린다. BFS는 모든 분기를 다 검색하면서 상태공간을 탐색한다. 철수가 이겼을 때, 비겼을 때, 졌을 때를 검사하고, 그 경우마다 각각 또다른 3가지 가능성을 전부 검사한다. 이러다가 어느 한 부분에서 원하는 해를 발견하면, 이것이 최단 거리가 된다.
BFS는 큐를 써서 구현한다. 각 경우를 검사하면서 발생하는 새로운 경우를 큐에 집어넣고, 검사한 원소는 큐에서 뺀다. BFS의 장점은 DFS가 못 건드리는 문제를 풀 수 있는 것이지만, 공간 복잡도가 지수 스케일로 폭발하기 때문에 가지치기를 제대로 안하면 DFS보다 빨리 오버플로우에 다다를 수 있다.
이 BFS에서 조금 더 발전한 방식이 Best First Search 방식이다. 큐 대신 우선순위 큐(보통은 힙으로 구현되는)를 써서 구현하는데, 발생하는 새로운 경우를 순차적으로 검사하는 Breadth First Search와는 달리 현재 가장 최적인 경우를 우선적으로 검사하므로 상대적으로 효율적이다. 백트래킹은 모든 경우를 다 고려하기 때문에 이걸 쓰면 어지간해서는 해결할 수도 있다. 다이나믹 프로그래밍으로 할 수 있는 것도 다 구현할 수 있으니 시간과 메모리만 해결하면 매우 유용하다. 해결하지 못했을 때 시간이 많이 걸려서 그렇지. 또한 무의미한 탐색을 막아줄 가지치기(Bounded(Promising) function)를 적용하여 적당한 지능(Heuristic)을 부여한다면 상당히 효과적인 해결방법이 될 수 있다. 아까 본 철수 영희 문제의 경우, 목적지점과 계속 반대로 가려는 가지는 굳이 탐색할 필요가 없으므로, 적절히 쳐내면 된다. 이렇게 하면 전혀 가망이 없는 경우로의 탐색이 이루어지지 않으므로 계산 성능이 향상된다.
백트래킹의 가지치기를 연습하고 싶다면 KOI에 나온 "공주님의 정원"이라는 문제가 있다. (미친듯이 코팅해야 답이 나온다.) (정해는 그리디 알고리즘)
일반적으로 특정 퀘스트나 스토리를 클리어하기 위해 게임을 진행한 뒤, 자동으로 초기 지점으로 돌아오는 기능 등이 없어 왔던 길을 플레이어가 직접 캐릭터를 조정해 처음부터 다시 돌아와야 되는 경우를 칭하는 말.
주로 어드벤처, RPG 요소가 있는 게임에서 적용되는데, 가장 대표적인 경우의 예시를 들자면 아래와 같다.
하지만 대부분의 게임에서 한 플레이어가 이렇게 플레이하게되는 퀘스트가 수십, 수백여개에 이른다는걸 고려하면 생각보다 상당히 짜증을 부르는 과정이다. 당연히 이미 퀘스트와 스토리에 관련된 것은 다 해결된 다음이기 때문에 플레이어에게 재미를 부여해줄 만한 부분이 거의 없어진 상태이니 그냥 의미 없이 시간만 소모하게 되는 과정이기 때문이다. 해당 게임이 패스트 트래블, 빠른 여행 기능이 없는 게임일 경우 이 스트레스는 몇 배로 더 강해진다. 거기다 스토리와는 관련이 없는 반복 퀘스트의 비중이 높을 수 밖에 없는 온라인 게임들의 경우는 그 짜증이 훨씬 더 심할 수 밖에 없다.
세심한 개발사의 경우 반복 퀘스트들의 경우 굳이 해당 NPC에게 돌아가지 않아도 퀘스트 창을 열어 클릭만 해도 임무를 완료할 수 있다거나, 퀘스트 완료와 동시에 플레이어 캐릭터를 그 NPC의 앞으로 빠른 이동시키는 등의 간편한 기능을 게임에 넣어두는 경우도 볼 수 있다. 그러나 많은 수의 제작사들이 플레이 타임을 좀 더 늘리기 위해서라도 굳이 이런 조치까지 취하지는 않는 경우가 많아 플레이어들에게 지탄을 꽤 많이 받는 편. 그럼에도 불구하고 게임 개발 기술이 과거와는 비교도 안될 정도로 향상된 2010년도에 이르러서도 백트래킹은 여전히 줄어들 기미가 보이지 않는다.
다만 오픈 월드 식의 샌드박스 게임의 경우, 대부분 방대한 게임의 필드를 직접 돌아다녀야 랜덤 인카운터나 새로운 지역 발견 등을 포함한 그 게임의 진정한 컨텐츠를 즐길 수 있는 경우가 많기 때문에 일부러 백트래킹을 조장하는 경향이 있다. 이런 게임들을 무조건 빠른 이동으로 주어지는 퀘스트만 후다닥 해결하며 플레이해서는 내재된 방대한 컨텐츠를 거의 건드려보지 못하기 때문에 진정한 재미를 못느끼게되는 경우가 많기 때문.
또한 서바이벌, 호러 요소가 있거나 난이도가 높은 게임에서도 백트래킹은 적극적으로 활용되는데, 이런 게임은 제한된 자원으로 강한 적을 마주한다는 컨셉때문에 당초 지점으로 돌아가는 것 역시 전략적 요소로 활용되고 게임적 재미이기 때문이다. 처음 통과할때도 다시 돌아가는 것까지 고려하면서 플레이해야하고 다시 돌아갈때도 최적의 동선과 최소한의 희생으로 성공하는 것이 목적이기 때문에 신중히 머리를 굴려가면서 플레이하고 그래서 재미가 배가되는 편.
메트로배니아처럼 숨겨진 루트를 뚫는 식으로 탐험 요소가 강화된 어드벤처 게임에서도 백트래킹은 적극적으로 활용된다. 기존에 갔던 장소라도 새로운 능력이나 아이템을 통하여 새로운 장소로 진입하거나 새로운 이벤트를 발생시킬 수 있기 때문에 탐험에 대한 게임적 재미를 배가시킨다. 때문에 이런 게임에서는 새로운 능력이나 아이템을 얻으면 과거 갔었던 장소에 가서 이것저것 시도해보는것이 정석.
1. 알고리즘에서의 백트래킹
모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. 그냥 뇌없이 짤 수 있다는 것이 장점이다.
모든 경우의 수를 고려해야 하는 문제라면[1], DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가(...). 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은 DFS를 써도 일단 답은 나온다.
그러나 DFS를 절대 쓰면 안되는 경우가 있는데, 트리의 깊이가 무한대가 될 때이다. 미로찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 탈출할 수 없게 된다. 물론 중복검사를 막기 위한 장치를 넣을 수도 있지만, 그럴 바에는 BFS가 편하다. 또 분기점 없이 길이만 죽어라 긴 길이 나타나면 스택 오버플로우가 발생할 수 있다. 위의 미로찾기도 4방향(또는 8방향)중 마지막으로 진입하는 방향으로만 갔을 때 도착점이 있다거나 하면 DFS는 느리다. 그리고 최단거리 구하기에서는 BFS를 사용하는게 편리하다.
1.1. DFS
DFS는 상태공간을 나타낸 트리에서 바닥에 도달할 때까지 한 쪽 방향으로만 내려가는 방식이다. 미로찾기를 생각하면 쉽다. 한 방향으로 들어갔다가 막다른 길에 다다르면(=트리의 바닥에 도착) 왔던 길을 돌아가서 다른 방향으로 간다. 이 짓을 목표지점(=원하는 해)이 나올 때까지 반복한다.
재귀함수로 구현할 수 있으며, 재귀함수에 익숙하지 않다면 스택을 써서 할 수도 있다.
1.2. BFS
BFS는 모든 분기점을 다 검사하면서 진행하는 방식이다. 철수와 영희가 계단에서 가위바위보를 하며 게임을 하고 있을 때, 철수가 원하는 지점에 갈 수 있는 최소 승리 횟수는 얼마인가? 같은 문제에서 효과를 발휘한다. 이 경우 DFS는 깊이가 무한인 경우에 빠져나오지 못하며, 중복 방지를 한다고 치더라도 올바른 해를 찾는데 시간이 많이 걸린다. BFS는 모든 분기를 다 검색하면서 상태공간을 탐색한다. 철수가 이겼을 때, 비겼을 때, 졌을 때를 검사하고, 그 경우마다 각각 또다른 3가지 가능성을 전부 검사한다. 이러다가 어느 한 부분에서 원하는 해를 발견하면, 이것이 최단 거리가 된다.
BFS는 큐를 써서 구현한다. 각 경우를 검사하면서 발생하는 새로운 경우를 큐에 집어넣고, 검사한 원소는 큐에서 뺀다. BFS의 장점은 DFS가 못 건드리는 문제를 풀 수 있는 것이지만, 공간 복잡도가 지수 스케일로 폭발하기 때문에 가지치기를 제대로 안하면 DFS보다 빨리 오버플로우에 다다를 수 있다.
1.3. 최선 우선 탐색
이 BFS에서 조금 더 발전한 방식이 Best First Search 방식이다. 큐 대신 우선순위 큐(보통은 힙으로 구현되는)를 써서 구현하는데, 발생하는 새로운 경우를 순차적으로 검사하는 Breadth First Search와는 달리 현재 가장 최적인 경우를 우선적으로 검사하므로 상대적으로 효율적이다. 백트래킹은 모든 경우를 다 고려하기 때문에 이걸 쓰면 어지간해서는 해결할 수도 있다. 다이나믹 프로그래밍으로 할 수 있는 것도 다 구현할 수 있으니 시간과 메모리만 해결하면 매우 유용하다. 해결하지 못했을 때 시간이 많이 걸려서 그렇지. 또한 무의미한 탐색을 막아줄 가지치기(Bounded(Promising) function)를 적용하여 적당한 지능(Heuristic)을 부여한다면 상당히 효과적인 해결방법이 될 수 있다. 아까 본 철수 영희 문제의 경우, 목적지점과 계속 반대로 가려는 가지는 굳이 탐색할 필요가 없으므로, 적절히 쳐내면 된다. 이렇게 하면 전혀 가망이 없는 경우로의 탐색이 이루어지지 않으므로 계산 성능이 향상된다.
백트래킹의 가지치기를 연습하고 싶다면 KOI에 나온 "공주님의 정원"이라는 문제가 있다. (미친듯이 코팅해야 답이 나온다.) (정해는 그리디 알고리즘)
2. 게임에서의 백트래킹
일반적으로 특정 퀘스트나 스토리를 클리어하기 위해 게임을 진행한 뒤, 자동으로 초기 지점으로 돌아오는 기능 등이 없어 왔던 길을 플레이어가 직접 캐릭터를 조정해 처음부터 다시 돌아와야 되는 경우를 칭하는 말.
주로 어드벤처, RPG 요소가 있는 게임에서 적용되는데, 가장 대표적인 경우의 예시를 들자면 아래와 같다.
- 특정 NPC에게서 퀘스트를 받는다.
- 지정된 지역으로 이동해 퀘스트를 완료한다.
- 퀘스트를 부여해준 NPC에게 다시 돌아가 퀘스트를 정리하고 보상을 받는다.
하지만 대부분의 게임에서 한 플레이어가 이렇게 플레이하게되는 퀘스트가 수십, 수백여개에 이른다는걸 고려하면 생각보다 상당히 짜증을 부르는 과정이다. 당연히 이미 퀘스트와 스토리에 관련된 것은 다 해결된 다음이기 때문에 플레이어에게 재미를 부여해줄 만한 부분이 거의 없어진 상태이니 그냥 의미 없이 시간만 소모하게 되는 과정이기 때문이다. 해당 게임이 패스트 트래블, 빠른 여행 기능이 없는 게임일 경우 이 스트레스는 몇 배로 더 강해진다. 거기다 스토리와는 관련이 없는 반복 퀘스트의 비중이 높을 수 밖에 없는 온라인 게임들의 경우는 그 짜증이 훨씬 더 심할 수 밖에 없다.
세심한 개발사의 경우 반복 퀘스트들의 경우 굳이 해당 NPC에게 돌아가지 않아도 퀘스트 창을 열어 클릭만 해도 임무를 완료할 수 있다거나, 퀘스트 완료와 동시에 플레이어 캐릭터를 그 NPC의 앞으로 빠른 이동시키는 등의 간편한 기능을 게임에 넣어두는 경우도 볼 수 있다. 그러나 많은 수의 제작사들이 플레이 타임을 좀 더 늘리기 위해서라도 굳이 이런 조치까지 취하지는 않는 경우가 많아 플레이어들에게 지탄을 꽤 많이 받는 편. 그럼에도 불구하고 게임 개발 기술이 과거와는 비교도 안될 정도로 향상된 2010년도에 이르러서도 백트래킹은 여전히 줄어들 기미가 보이지 않는다.
다만 오픈 월드 식의 샌드박스 게임의 경우, 대부분 방대한 게임의 필드를 직접 돌아다녀야 랜덤 인카운터나 새로운 지역 발견 등을 포함한 그 게임의 진정한 컨텐츠를 즐길 수 있는 경우가 많기 때문에 일부러 백트래킹을 조장하는 경향이 있다. 이런 게임들을 무조건 빠른 이동으로 주어지는 퀘스트만 후다닥 해결하며 플레이해서는 내재된 방대한 컨텐츠를 거의 건드려보지 못하기 때문에 진정한 재미를 못느끼게되는 경우가 많기 때문.
또한 서바이벌, 호러 요소가 있거나 난이도가 높은 게임에서도 백트래킹은 적극적으로 활용되는데, 이런 게임은 제한된 자원으로 강한 적을 마주한다는 컨셉때문에 당초 지점으로 돌아가는 것 역시 전략적 요소로 활용되고 게임적 재미이기 때문이다. 처음 통과할때도 다시 돌아가는 것까지 고려하면서 플레이해야하고 다시 돌아갈때도 최적의 동선과 최소한의 희생으로 성공하는 것이 목적이기 때문에 신중히 머리를 굴려가면서 플레이하고 그래서 재미가 배가되는 편.
메트로배니아처럼 숨겨진 루트를 뚫는 식으로 탐험 요소가 강화된 어드벤처 게임에서도 백트래킹은 적극적으로 활용된다. 기존에 갔던 장소라도 새로운 능력이나 아이템을 통하여 새로운 장소로 진입하거나 새로운 이벤트를 발생시킬 수 있기 때문에 탐험에 대한 게임적 재미를 배가시킨다. 때문에 이런 게임에서는 새로운 능력이나 아이템을 얻으면 과거 갔었던 장소에 가서 이것저것 시도해보는것이 정석.
[1] 예를 들어 nQueen의 일반적인 해