[개념정리] 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라면 이와같은 그림이 될 것이다. 유망한 노드라면 자식노드로 들어가 다시 탐색을 시작할 것이고 유망하지 않다면 탐색을 그만두고 부모노드로 올라가서 다음 노드를 탐색할 것이다.

코딩뚠뚠