백트래킹과 가지치기에 대해서 예제 문제를 통해 알아봅시다.

 제가 개최한 대회 중에, 2번 문제는 브루트 포스, 백 트래킹을 이용한 문제였습니다. 코딩 테스트에서 상당히 자주 보이고, 반드시 풀고 넘어가야 하는 유형이므로, 2번에 출제하였습니다. 보통, 백트래킹이라고 하면, dfs를 돌리면서 처리하는 경우가 일반적입니다. 이 문제도 예외는 아닙니다. 문제는 중복 방문하는 것을 어떻게 처리할 것인지였습니다. 예를 들어, (1, 1)에 고구마가 있는데, (1, 1)을 3번 방문했다면, (1, 1)에 있는 고구마를 한 번 먹은 것이지, 세 번 먹은 것이 아니기 때문입니다.

 

 여기서 언급하는 문제는 실버1에서 골드5 정도로 그렇게 어렵지 않습니다. 그렇기에 더 자세히 분석해 보도록 하겠습니다.

 

---

 가장 먼저 생각할 수 있는 방법은, 중복된 데이터를 제거하는 방법이 있습니다. 중복 데이터를 제거하는 자료 구조는 어디서 많이 들어보시지 않았나요? c++에서는 map, set, unordered_map, unordered_set, 자바에서는 TreeMap, TreeSet, HashMap, HashSet이 있고, 파이썬에는 set, dict이 있어요.

 

 예를 들어 데이터 구조 안에 5, 7, 3이 있다고 해 보겠습니다. 5가 들어오려고 합니다. 5는 이미 있습니다.

 

 따라서, 데이터 구조에 5가 추가되지 않습니다. 단순 Array 같았으면, 5, 7, 3, 5가 리스트에 있었을 겁니다. 하지만, 중복을 제거하는 구조는 그렇지 않아요. 키 값이 있는지 검사하고 없으면 새로 추가하고, 있으면 업데이트를 하거나, 키 값을 추가하지 않습니다. 그런데, 해당 문제에서는 x 좌표와 y 좌표가 들어와요.

 

 

 (2, 5), (3, 2), (4, 1) 이런 식으로 데이터가 들어올 겁니다. 이런 것을 표현하는 클래스가 c++에는 pair가 있습니다. 파이썬에는 tuple이 있어요. 자바에는 그런 게 있나요? 잘 모르겠습니다. 지원하지 않는 걸로 알고 있어요. 그런 경우에는 어떻게 하면 좋을까요? 2개의 필드로 이루어진 데이터를 int나 long long형으로 압축하면 됩니다. 아래 그림을 보세요. 

 

 저는 (2, 5)를 2M+5로 압축했어요. M은 맵의 최대 가로, 세로 크기보다 더 큰 202로 잡았습니다. 그러면, (4, 1)은 4M+1로 압축이 가능합니다. (3, 2)가 추가로 들어온다면, 3M+2를 데이터 구조에 넣으면 됩니다.

 

 이것은 이미 있습니다. 따라서, 중복 처리가 되게 됩니다. 문제의 의도인 dfs로 풀지 않고, 그냥 단순히 모든 경우의 수를 brute force로 돌리고, visit 처리를 맵으로 한 풀이도 통과가 됩니다. 500ms 정도로요.

 

 

---

 그런데, c/c++로 통과하신 분들의 시간을 보면 0ms, 12ms가 굉장히 많이 보입니다. 이는 모든 경우의 수를 brute force로 돌리면서, visit 처리를 맵으로 한 것보다 효율적인 풀이가 있다는 이야기입니다.

 

 

 3by3 데이터가 ["###", "#GS", "#S#"] 요래 주어졌다고 생각해 봅시다. 그러면, 처음에 왼쪽으로 가는 것이나 위로 가는 것은 올바른 경로가 아닙니다. 그럼에도 불구하고, 링크는 그러한 경우까지 모두 전수탐색을 하고 있음을 알 수 있어요. 즉, 처음에 위로 올라가는 것이나, 왼쪽으로 가는 경우는 가지를 쳐도 된다는 이야기입니다.

 

 

 이렇게 하게 되면, 탐색하는 경우의 수를 반으로 줄일 수 있어요. 그런데, G가 중앙에 있고, 택시 거리로 T 이내인 위치에 #이 없는 경우는 효율이 없는 게 아닌가요? 이 때에는 탐색하는 경우의 수가 반으로 줄어들지 않습니다. 그럼에도 의미가 없는 것은 아닙니다. 기존 코드가 너무 비효율적이였기 때문입니다.

 

 

 다시, 기존 코드를 보면, 4^T가지 경우에 대해서, 뭔가 작업을 하고, gogo를 호출함을 알 수 있는데요. gogo를 봅시다.

 

 길이가 T인 이동 경로에 대해서, 처음 부터 탐색함을 알 수 있어요. 게다가 visit를 set으로 관리했어요. 여기서 중요한 핵심은, set이 느리다는 것이 아닙니다. set이 느린 것은 당연하고요. 재활용 할 수 있는 정보를 재활용 하지 않고, 처음 위치부터 돌아버렸다는 것입니다.

 

 

 예를 들어, Right - Left 경로로 갔을 때, 고구마를 얼마나 먹었는지를 구했다고 해 봅시다. 이 때에는 2번 탐색하면 됩니다.

 

 

 다음에, RIght - Down 경로로 갔을 때는 어떨까요? 이 경우에도 2개의 노드를 검사한다는 것이 문제입니다. 이전에 Right - Left 경로로 간 것에 대한 정보를 얻었다면, Right - Down 경로에 대해서 2개의 노드를 검사할 필요가 있을까요?

 

 

 처음에 Right 한 번 간 것에 대한 정보를 저장했다면, 중복으로 계산할 이유가 없습니다.

 

 

 Right - Right - Right - Right - Left로 온 경우에 대해서 먹은 고구마의 갯수를 계산하였습니다. 그 다음에 Right - Right - RIght - Right - Down으로 온 경우에 대해서 몇 개나 먹었는지를 계산할 건데요. 여기서 중요한 것은 우측으로 4번 간 경우에 대해서도 이미 이전에 계산이 되었다는 것입니다. 만약에 미리 정보를 저장하고 있다면, 이미 계산된 경우, 노란색으로 표시된 것에 대해서 또 계산할 필요가 없습니다.

 

 중복해서 계산을 하는 것이 비효율적인 것은 알았습니다. 이제, 정보가 누적되었을 때 어떻게 처리해야하는지를 고민해야 합니다. 두 번 이상 방문하였을 때, 고구마를 먹은 갯수가 중복해서 세지 않게 하려면, (x, y)를 몇 번 방문하였는지를 count 하여야 합니다.

 

 

 이 처리는 vis[cx][cy]에서 하고 있어요. 만약에 (cx, cy)에 방문하지 않았으면서, 해당 위치에 고구마가 있으면, 답을 하나 더한다는 것을 알 수 있어요.

 

 그러면, (cx, cy)를 한 번 더 방문하였을 때에는, (cx, cy)의 방문 횟수를 하나 늘려주면 됩니다. 원복을 할 때에는, (cx, cy)에 방문한 횟수를 하나 빼면 됩니다. 간단한가요? 우리는 중복 처리를 고민했다기 보다는, 고구마가 있는 특정 위치를 몇 번 방문하였는지에 따라서, 고구마를 답에 더할 지 말아야 할 지를 결정했을 뿐입니다. 여기까지 적용한 코드는 링크를 보시면 됩니다.

 

 

---

 추가로 가지치기를 할 수 없을까요? 가희가 t개의 위치를 방문했을 때 고구마를 cur_ans개만큼 먹었다고 해 보겠습니다.

 

 

 ?는 어느 위치에 도달할지 모르는 상태라고 해 보겠습니다. ?는 T-t개 나올 수 있어요. 그러면, 이 상태에서 가희가 T-t개의 위치를 더 방문했을 때, 최종적으로 고구마는 몇 개 까지 먹을 수 있을까요?

 

 이 경우에, cur_ans + (T-t)만큼 먹을 수 있을 겁니다. 그런데 이 값이 기존에 알려진 최대로 먹을 수 있는 고구마 수보다 작거나 같다면 더 탐색할 이유가 있을까요? 그렇지 않을 겁니다. 이 상태에서는 어떻게 먹어도 기존에 알려진 최대로 먹을 수 있는 고구마보다 많이 먹을 수 없습니다. 이는 '유망하지 않는 경우'이고, 이러한 경우를 걸러내는 것을 가지치기 한다고 합니다. 이것까지 적용한 코드는 링크를 보시면 됩니다.