[Algorithm Tech] BackTracking

* BackTracking

왔던 길을 되추척하는 방법

BackTracking 과 DFS는 비슷하지만 다른 차이점이 있다.

DFS 의 경우 방문한 점을 다시 방문하지 않는다는 특징이 있지만,

BackTracking 의 경우는 방문한 점을 다시 방문할 수 있다.

>> DFS는 순서의 상관 없이 M개중에서 N개를 뽑을 때 사용

>> BackTracking은 M개 중에서 N개를 순서에 따라 뽑을 때 사용

* BackTracking 시간 복잡도 

BackTracking 의 시간 복잡도는 O(2^n) 이다.

N의 범위가 보통 26 이하인 경우 사용 가능하다.

* BackTracking 유의할 점

DFS와 다르게 방문한 점을 다시 방문할 수 있기 때문에, 방문 이후 boolean visied 값을 초기화작업 필수

* BackTracking 작동 방식

Ex) 4개의 선택지가 있고, 선택시 1, 미선택시 0이라고 가정할 때, 작동 순서는 다음과 같다.

0

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

마지막 선택지의 경우 이미 다녀온 경우에도 불구하고 앞에 선택지가 변경되면 마지막 선택지를 다시 방문해야 한다.

BackTracking 의 경우 위와 같은 방식으로 진행된다.

이를 Tree 구조로 나타내면 다음과 같다.