Backtracking Algorithm

Backtracking 백트래킹 알고리즘 (퇴각 검색)

https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89

내가 생각한 백트래킹 알고리즘은 "모든 경우"를 다해본다는 느낌이 강하다. 

백트래킹에서 중간 cutting을 잘 만들면 속도를 많이 개선 할 수 있고, 대표값을 설정하면 다이나믹과 비슷한 효과도 낼 수 있다.

내 생각엔 백트래킹 기법이 가장 기초적이고 중요한 기법이라고 생각한다.

백트래킹을 배우는 사람에게 늘 하는 말이 있다. 모든 문제는 백트래킹으로 해결 할 수 있다고 늘 얘기한다.

결국 모든 것을 다해보면 모든 문제를 풀수있다. 하지만 시간이 오래걸리고 메모리도 많이 잡아먹는 해법이 될것이다. 

그렇기 때문에 다른 알고리즘이 필요한것이다. 특정 상황에 효율적인 알고리즘을 사용하면 더 빠르고 좋은 결과를 나타낼 수 있다.

대부분 backtracking 알고리즘을 재귀를 이용해서 접근 하거나 Queue를 이용해서 접근한다.

"모든경우를 다해본다." 이부분에서 부터 이해가 안되실 수 있는데, 무엇인가 선택을 해야할 때, 선택할 수 있는 모든경우를 하나씩 다 해보는 것이다.

예를 들어

사람이 n명일 때, "베스킨라빈스 31"게임을 한다고 했을 때 게임이 돌아가는 모든 경우의수를 구하는 프로그램을 만든다고 하자.

 

( 한사람씩 돌아가면서 숫자를 외치는 게임이고, 1부터 시작해서 31을 외치면 지는 게임이다.

 자신의 차례의 경우 , 앞사람이 외친 수의 마지막 수 + 1 부터 외칠수 있고, 연속된 숫자를 외쳐야 하며, 최대 3개까지 한번에 외칠 수 있다.

1번사람 => 1

2번사람 => 2, 3

3번사람 => 4, 5

4번사람 => 6, 7, 8 

(4명밖에 없다면) 1번사람 => 9, 10, 11

이런 순으로 돌아가는 게임이다.)

모든것을 해본다는건 각사람이 상황에 외칠 수 있는 총 3개의 방법을 

맨처음에 1번사람이 처음 시작한다면 외칠 수 있는 방법은 1 혹은 1, 2 혹은 1, 2, 3 이다.

백트랙킹은 3가지 경우를 모두 해보는 것이다! 이걸 재귀로 나타낸다면

---

Sample Code:

int countAll ( int person_num, int called_num, int n ){

// person_num => 현재 사람 번호 0 ~ n - 1,  called_num => 앞사람이 부른 마지막 번호,  n => 총 사람수

// 끝나는 조건을 설정 해준다. 이 문제 같은경우는 31이 불렀을 때 이다.

if(called_num == 31){

// 앞에서 31을 이미 불렀기 때문에 

return 1; // 이 상황에서는 부르지 않고 게임이 끝났기 때문에 1가짓수라고 할 수있다.

}

// 끝나는 조건이 아닌경우 

int person_num_next = ( person_num + 1 ) % n; // 다음번 사람 번호를 찾음

int total = 0;

total += countAll(person_num_next, called_num + 1, n ); // 한개를 불렀을 경우

if( called_num + 2 <= 31)

total += countAll(person_num_next, called_num + 2, n); // 두개를 불렀을 경우 

if( called_num + 3 <= 31)

                total += countAll(person_num_next, called_num + 3, n); // 세개를 불렀을 경우 

return total;

}

---

위와 같은 식으로 함수에서 자신을 재귀로 부르면서 다음상태를 취해가는 방식이다. 

결국 재귀를 통해 시작 상태에서 => 모든 선택의 경우를 다 돌면서 모든 경우를 탐색한다.

---

Queue 를 이용한 접근은 

Sample Code:

int countAll( int n ){

Queue<pair<int,int>> queue;  // pair< x, y > : x => 다음사람 번호, y => 마지막에 부른 수.

queue.push_back(make_pair( 0, 0 ) )

pair<int,int> now;

 int person_num, called_num, person_num_next ,total = 0;

while(queue.size() != 0){

now = queue.pop_front();

person_num = now.first;

person_num_next = (person_num + 1) % n;

called_num = now.second;

if(called_num == 31){

total += 1;

}

if(called_num + 1 <= 31){

queue.push_back(make_pair( person_num_next, called_num + 1);

}

if(called_num + 2 <= 31){

queue.push_back(make_pair( person_num_next, called_num + 2);

}

if(called_num + 3 <= 31){

queue.push_back(make_pair( person_num_next, called_num + 3);

}

}

return total;

}

---