[Algorithm] 백트래킹 기법

이번 포스팅에서는 백트래킹 방법(Backtracking)에 대해서 알아보겠습니다.

1.백트래킹이란?

정의

: 해를 찾는 도중에 ‘막히면’(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 즉 모든 경우의 수를 전부 고려하는 알고리즘이다.
일종의 트리 탐색 알고리즘이라고 봐도 된다.
방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS)로 나뉜다.

1.1 DFS(Depth First Search) - 깊이우선탐색

: DFS는 상태공간을 나타낸 트리에서 바닥에 도달할 때까지 한 쪽 방향으로만 내려가는 방식이다. 미로찾기를 생각하면 쉽다. 한 방향으로 들어갔다가 막다른 길에 다다르면(=트리의 바닥에 도착) 왔던 길을 돌아가서 다른 방향으로 간다. 이러한 방법을 목표지점(=원하는 해)이 나올 때까지 반복한다. 재귀함수로 구현할 수 있으며, 재귀함수에 익숙하지 않다면 스택을 써서 할 수도 있다.

1.2 BFS(Breadth First Search) - 너비우선 탐색

: BFS는 모든 분기점을 다 검사하면서 진행하는 방식이다.
철수와 영희가 계단에서 가위바위보를 하며 게임을 하고 있을 때, 철수가 원하는 지점에 갈 수 있는 최소 승리 횟수는 얼마인가? 같은 문제에서 효과를 발휘한다. 이 경우 DFS는 깊이가 무한인 경우에 빠져나오지 못하며, 중복 방지를 한다고 치더라도 올바른 해를 찾는데 시간이 많이 걸린다. BFS는 모든 분기를 다 검색하면서 상태공간을 탐색한다. 철수가 이겼을 때, 비겼을 때, 졌을 때를 검사하고, 그 경우마다 각각 또다른 3가지 가능성을 전부 검사한다. 이러다가 어느 한 부분에서 원하는 해를 발견하면, 이것이 최단 거리가 된다.

BFS는 큐를 써서 구현한다. 각 경우를 검사하면서 발생하는 새로운 경우를 큐에 집어넣고, 검사한 원소는 큐에서 뺀다. BFS의 장점은 DFS가 못 건드리는 문제를 풀 수 있는 것이지만, 공간 복잡도가 지수 스케일로 폭발하기 때문에 가지치기를 제대로 안하면 DFS보다 빨리 오버플로우에 다다를 수 있다

1.3 예시

• 미로 찾기, n-Queen, Map coloring, 부분 집합의 합
• 입구에서 출구까지 가는 경로가 존재하는지 묻는 문제
• 원소의 합이 조건에 맞는 부분 집합이 존재하는지 묻는 문제
• 미로 찾기에서 출구까지 가는 경로 중에 최단 경로를 찾는 문제
• 가지치기로 불필요한 경로 조기에 차단