[Algorithm] 백트래킹(Backtracking)

1. DP vs Backtracking

DP는 problem과 sub-problem을 나누어 진행하고, 이 sub-problem은 더 작은 sub-problem으로 나누어 질 수 있다. 겹치는 sub-problem은 memorization을 통해 저장하면서 중복된 계산을 줄여갔다.

그러나, Backtracking은 우리가 가져갈 수 있는 모든 경우의 수를 하나씩 살펴보고, Decision space를 만들어 나간다. 여기서 어떠한 경우의 수가 의미가 없게되면 가지치기를 하게 되고 backtracking을 하면 된다. 

2. Backtracking

ex> Phone keypad 문제(leetcode 17)

우리가 아는 휴대폰의 키패드는 아래의 사진과 같다. 

Phone Keypad 예시

"25"가 입력이 되었을 때, AJ / AK / AL / BJ / BK / BL / CJ / CK / CL라는 알파벳이 나올 수 있다. 여기서 HashMap으로 예를 들자면, {1 : null, 2 : [a, b, c], 3 : [d, e, f] ... , 9 : [w, x, y, z]}가 된다. 숫자는 key값이 되고, 알파벳은 value가 된다. 이때 "259"라는 숫자가 input으로 들어왔다는 가정을 해보자. 

2같은 경우는 [a, b, c] 가 있는데 이 세 가지 모두가 decision space가 된다. 이처럼 가지를 내려가면 아래의 그림처럼 경우의 수를 나타낼 수 있다. 

259 입력의 예시

실제 코드는 당연히 하나의 단계씩 진행될 것이다. 이를 모든 경우로 정리해보면 ajw, ajx, ... 이런식으로 할 수 있다. DP같은 경우는 DP Array, Table을 채워나간다고 생각하면 구현가능하지만, Backtracking은 위의 그림을 코드로 나타내기에는 어려울 수 있다. 우리는 위의 내용을 코드로 쉽게 확인하기 위해 수도 코드를 확인할 수 있다. 

input : input (ex> "259")
output : output

def Backtracking(index : 몇번째 숫자인지, letter(depth) : 몇번째 단계까지 만들어졌는지) {
  // 초기 index는 0, letter은 ""
  if (index >= input의 length) {
    output.add(letter)
  }

  num = input[index]
  chars = Hashmap[num] <- a, b, c / j, k, l / w, x, y, z
  for (c : chars) {
    Backtracking(index + 1, letter + c) // 재귀
    erase(c) // 백트래킹이 끝난 경우 c를 지워주는 코드를 넣어야 함
  }
}

이론 자체는 어렵지 않지만, 많이 응용해보고 연습해야 손에 익을 것 같다. 

 

---

참고문서

https://www.youtube.com/watch?v=Ar40zcPoKEI