백 트래킹이란?

백 트래킹은 DFS의 일종으로 저번 재귀를 사용한 알고리즘의 일종이다.
여러 선택지 중, 가능한 모든 경로를 탐색하고 조건에 맞지 않은 것을 배제하며 값을 찾아 나간다.

여기서 조건에 맞지 않는 것을 배제하는 것을 가지치기라고 한다.

가장 중요한 것은 역시 "제약조건"인데 이를 제대로 설정하지 않는다면 문제가 발생한다.

DFS

여기서 일반적인 DFS를 알아야 백트래킹을 더 잘 이해할 수 있다.

DFS란 Depth-First Search의 약자로 한국어로 직역하면 깊이 우선 탐색 알고리즘이라고 한다.

즉, 시작 지점부터 끝지점을 찍고 돌아오는 방식이라고 보면 된다.

DFS는 백트래킹에서 가지치기를 뺀다고 생각하면 좋다.

백트래킹과 DFS의 차이

백트래킹은 DFS에서 가지치기를 뺴고, DFS는 백트래킹에서 가지치기를 한다라고 표현하니 조금 어려울 수 있다

사실 DFS와 백트래킹의 차이가 굉장히 모호함에 그 이유가 있다

특히,, 거의 유사하다고 생각이 들 정도이다.

간단하게 말하면 백트래킹은 경로를 필요없다고 판단한다면 해당 경로를 포기(가지치기)하는 것이다.

가장 간단한 예시를 들어 보겠다.

		1
	3
    	4
5
		7
	8
		9

모든 수는 자연수라고 하였을ㄷ 때, 최상단 노드가 5이고, 최 하단에 1 4 7 9, 그 중간에는 3 8이 있다는 한 트리가 있다고 가정을 하자
이 때, 우리는 합이 12가 되는 경로가 있는지 찾는 것이다.

DFS는
5 -> 3 -> 1 = 9
5 -> 3 -> 4 = 12 (찾음)
5 -> 8 -> 7 = 20
5 -> 8 -> 9 = 22
이러한 결과값을 도출한다.
그런데 한가지 의문점이 들 것이다

5 -> 8 에서 이미 13이 넘어 12가 될 수 없는데.. 여기서 탐색을 멈추게 하면 안되나..?

그렇게 해서 조건을 넣게 된 것이 백트래킹의 과정이라고 볼 수 있다.

결과 값이 12를 넘을 수 없다는 "제약 조건"을 넣어서 해당 루트를 배제하는 "가지치기"를 진행하는 것이다.

결론

사실 처음 백트래킹을 보고는 무슨 말인지 도무지 이해가 가질 않았다.
DFS와의 차이도 전혀 이해를 하지 못했다..
그러나 백트래킹은 일반적인 DFS에 비해 계산과정을 현저하게 줄여 준다.
만약 재귀를 사용해야하는 상황이라면 이를 잘 활용하여 문제를 푼다면 시간에서 큰 이익을 볼 수 있을 것이다.

해당 알고리즘을 이해하고 활용하기 위한 두 문제를 추천한다.
사실 백준 단계별 풀어보기에 있는 문제이지만.. ㅎㅎ

N-Queen
Sudoku

해당 문제들을 풀면 제약 조건을 얼마나 명확히 해야하는지 깨닫게 된다.

기존 값으로 되돌리려는 backtracking의 특성상 해당 값이 최종 값에 도달하면 초기화 되버릴 수 있게 때문에 이를 방지하려는 과정이 필요하기 때문이다..!

나는 변수를 하나 두어 이를 통해 마지막에 초기화할 수 없게 return을 해주는 방식을 채택하였다.