백트래킹 : 모든 경우를 탐색한다.

 백준 사이트에 있는 구현 문제는, 대다수가 브루트 포스로 풀리는 경우가 많습니다. 코딩 테스트를 준비하시는 분들도 적지 않으실 거 같은데요. 그것들을 잘 풀기 위해서, 이론적인 지식 3~4편 정도만 올리고, 실전에 들어가도록 하겠습니다. 백트래킹 탐색은, 다음과 같은 알고리즘으로 동작합니다.

 

 뭔가 복잡해 보이는데요. 제일 중요한 부분은, (1)번과 (3)번, (5)번이라고 할 수 있어요. 이 셋만 잘 작성하면 끝났다고 볼 수 있어요. 그런데, 아직 이해가 안 가는 부분이 많습니다. 들어올 수 있는 상태들은 대체 무엇을 의미할까요? 예를 들어, 스토쿠를 생각해 봅시다. 빈칸에 숫자를 넣어야 할 때, 1부터 9까지만 넣을 수 있어요. 즉, 우리가 빈 칸에 넣을 수 있는 숫자들의 집합은 {1, ... , 9}입니다. 이를, 들어올 수 있는 상태들이라고 이야기를 합니다. back tracking 알고리즘을 구현하기 위해서는, 이 상태들을 잘 정의하는 것부터 해야 합니다.

 

 

---

 이것만 보면 잘 이해가 가지 않을 듯 싶습니다. 한 가지 예를, 차근 차근 설명해 보도록 하겠습니다. {1,2,3,4}의 순열을 모두 출력하려고 합니다. 어떻게 해야 할까요?

 

 

 먼저 네모칸에 들어갈 수는 어떤 것들인가요? 1, 2, 3, 4입니다. 즉 상태에는 {1, 2, 3, 4}가 저장이 되어 있습니다.

 

 

 코드를 봅시다. 저는 state에 1부터 4까지를 넣고 있어요. 그러면 이것은 state라는 집합에 1, 2, 3, 4가 들어갔다는 것을 의미해요. 따라서, 들어올 수 있는 상태에 대해서 탐색을 할 때에는, state 벡터에서 탐색하면 됩니다.

 

 

 그러면, (3)번은 채웠습니다. 그러면, 상태는 어떻게 넣어보면 될까요? back의 cur_depth는, 현재 ans 배열에 넣어볼 위치를 의미합니다. main 함수에서 back(0,4); 를 호출했는데요. 이는 ans 배열의 0번째 위치에 수를 넣어보겠다는 의미입니다.

 

 

 back의 1번쨰 인자는 cur_depth입니다. 이것이, 현재 수를 채워 넣어야 할 위치를 가지고 있습니다.

 

 

 따라서 (4)번에는 ans[cur_depth] = cur_state가 들어가면 됩니다. 그러면, (5)번, 현재 넣은 상태가 vaild 한지 체크는 어떻게 하면 좋을까요? 예를 들어, cur_depth가 2라고 해 봅시다. 그리고 ans에는 다음과 같이 들어갔다고 해 봅시다.

 

 

 vaild 한가요? 아닙니다. 왜 아닌가요? {1, 2, 3, 4}의 순열은, {1, 2, 2, x}가 될 수 없기 때문이에요. 2가 중복해서 나와 버렸어요. 이걸 어떻게 판단하면 좋을까요? 보라색 부분의 구간은 [0, cur_depth-1]로 표현할 수 있어요. 이 구간에서 2가 나오는지 보면 되는데요. 만약에 나온다면, 나오는 위치를, 안 나온다면 -1을 리턴하게끔 합시다.

 

 

  find(s,e,a)는 구간 [s,e]를 탐색했을 때, a가 나타나는 위치를 리턴하는 함수입니다. 만약에 없다면 -1을 리턴합니다. 그러면, 5번 조건에는 if(find(0,cur_depth-1,cur_state) == -1)이 들어가면 좋겠네요. 왜냐하면 [0, cur_depth-1]을 보았을 때, 문제의 값인 cur_state가 없으면 될 테니까요.

 

 

 그러면, back을 호출하면 되는데요. 몇 번째 위치를 채워 넣어야 하나요? cur_depth는 이미 채워 넣었기 때문에 c_d+1 위치에 있는 칸에 수를 넣어야 합니다.

 

 

 (5), (6)을 채우면 위와 같습니다. (7)이 문제인데요. 원상 복구를 시키려면 어떻게 해야 하나요? cur_depth번째에 수를 채워넣지 않은 상태가 원래 state였으니, 0을 넣으면 됩니다. 여기까지 대략적인 흐름도가 이해가 되시나요?

 

 

---

 그런데 우리는 답이 될 수 있을 때, 출력을 하지 않았습니다.

 

 

 ans[3]까지 채웠다고 해 봅시다. 그러면, 그 다음에 back(4,4)를 호출할 겁니다. 4개를 채웠고, 수를 4개 채워 넣어야 합니다. 그런가요? cur_depth하고 mok_depth하고 같아지는데요. 이 때, 우리는 ans 배열을 조건에 맞게 채웠다고 볼 수 있어요. 따라서 1번에는 cur_depth == mok_depth를 넣어주시면 됩니다.

 

 

 이 때, ans에 들어있는 내용들을 모두 출력하면 됩니다. 이제 back 함수의 전체 코드를 봅시다.

 

 

 먼저 16번째 줄부터 26번째 줄 까지는 답이 될 수 있는지를 판단합니다. cur_depth가 x인 경우에, ans에 x개가 채워져 있다는 것이고, mok_depth는 몇 개를 채워야 하는 가를 나타낸다고 했었습니다. 이 두 값이 같다면, 답이 될 수 있기 때문에, 출력만 하고 빠져나오면 됩니다.

 

 

 그렇지 않다면, state 집합을 돌면서, 상태를 넣어본다고 했습니다. 넣었을 때, 유효한지 판단을 해야 한다고 했습니다. 이 문제에서, vaild 하지 않은 경우는 어떤 경우인가요? 2가 있는 상태에서, cur_depth번째에 2를 넣은 경우에 2가 2번 들어갔으니까 유효하지 않습니다. 즉, [0, cur_dep-1]까지 보았을 때, 내가 넣어볼 수인, cur_state가 없다면, 백트래킹을 합니다. 그리고 42번째 줄에서, 상태를 원상 복구 하고 있어요.

 

 큰 그림만 이해하셔도 무난하리라 생각이 듭니다. 다음 시간에 응용 문제 1개만 풀어보도록 하겠습니다.