[개념정리] Backtracking 백트래킹

 

백트래킹 (Backtraking) 이란

​

기본적으로 가능한 모든 방법을 탐색하기 위해 고안된 아이디어이다. 완전 탐색을 위해서는 DFS를 사용할 수 있다. DFS는 모든곳을 방문하기때문에 굳이 목표지점이 있지 않은 경로로 빠져서 자칫 비효율 적일 수도 있다.

​

이런 비효율성을 개선하기 위해 옳지 않은 경로를 차단하고 목표지점에 갈수있는 가능성을 가진 루트만 검사하는 것이 백트래킹 알고리즘이다. DFS에 가지치기를 옳을 가능성이 높은 방향으로만 치게하는 것.

​

프로그래밍에서 가지치기란 break 나 return 등 으로 구현할 수 있다.

​

​

예시1

 

 

이렇게 생긴 경로가 생성되어있다. 1에서 출발하여 문자열을 붙여가며 15에 도착했을때 "1 3 9 15"하는 것이 목표이다.

​

dfs를 실행하면 1->2 로 시작할 것이고 순간 문자열은 "1 2"로 만들어질 것이다. 정답의 문자열의 시작인 "1 3"과는 다르기 때문에 1->2의 경로는 과감히 포기하고 1->3을 들여다본다.

​

1->3->9->15 의 경로를 찾을 수 있을 것이다. 최악의 경우 모든 경로를 들여다 봐야하는 dfs에서 개선이 된 것을 알 수 있다.

​

​

예시2

 

백트래킹을 설명하는데 유명한 문제라고 하는 N-Queen 문제이다.

​

N*N 체스판에 N개의 Queen을 놓고싶다. 다만, 서로를 공격하지 않게 올려놓고싶다. 총 몇가지 경우의 수가 있을까?

- Queen은 동서남북 뿐아니라 대각선 즉 8방으로 움직일 수 있다.

​

방법1.

모든 조합의 경우를 센다. 체스판 왼쪽부터 queen을 차례대로 두면 한 열에 하나의 queen밖에 놓지못한다. 즉 모두 살펴보면 경우의 수는 N^N개가 될 것이다. 으로 시간복잡도는 O(N*N)일 것이다. 비효율적.

​

방법2.

백트래킹으로 풀이해보자. 만약 N=4라면 이와같은 그림이 될 것이다. 유망한 노드라면 자식노드로 들어가 다시 탐색을 시작할 것이고 유망하지 않다면 탐색을 그만두고 부모노드로 올라가서 다음 노드를 탐색할 것이다.

 

그림 출저: http://ddmix.blogspot.kr/

​