백트래킹(Backtracking)
일반적인 알고리즘이다.
백트래킹은 CSP(Constrain Staisfaction Problems)을 해결하기 위해 쓰인다.
백트래킹은 모든 조합의 수를 조건이 만족할 때 살펴본다.
N-Queen문제에서 많이 사용된다.
N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
4 * 4 기준으로 문제를 풀어보자.
퀸은 칸을 기준으로 오와 열, 대각선 이동이 가능하다.
첫 번째 퀸과 공격할 수 없게 배치할려면 2번째 줄은 3, 4번째 위치에 퀸을 놓아야 한다.
첫 번째 퀸의 위치를 (1, 1)로 하면 트리구조는 다음과 같다.
만약 이문제를 가지치기 하지않는 DFS로 풀이했다면 유망하지 않는 (2,1), (2,2) 지점도 검사를 했을 것이다.
이럴 경우, 더 큰 체스판에서 퀸을 놓는 경우의 수를 찾을 때 수많은 연산이 일어나게 된다.
(가지치기를 잘해야 한다.)
백트래킹 4가지 절차 예시
1) DFS 수행 : 먼저 평소와 같이 깊이우선탐색인 DFS를 수행하여 노드를 찾는다.
2) 유망한 노드 검토 : 방문한 노드를 포함해서 유망한 노드이면 서브트리로 이동하고 그렇지 않으면 백트래킹을 수행한다.
3) 방문한 노드의 하위 노드로 이동하여 다시 재귀를 통해 DFS를 수행한다.
4) 백트래킹 수행 : 방문한 노드를 가지치기를 하고 상위 노드로 백트래킹 한 후 DFS를 다시 수행한다.
ex) 백트래킹 4가지 절차를 이용하여, 2번 째 위치에 퀸을 놓는 방법
1) (1, 1) 에서 시작하여 DFS 수행을 통해 가장 첫번째 노드인 (2, 1) 지점으로 간다.
2) (2, 1) 노드를 검사해보니 첫번째 퀸의 이동반경에 포함되기 때문에 유망한 노드가 아니어서 백트래킹을 수행하여 상위 노드인 (1, 1) 지점으로 이동한다.
3) 다시 DFS 를 수행하여 다음 노드인 (2, 2) 로 이동한다.
4) (2, 2) 노드를 검사해보니 첫번째 퀸의 이동반경에 포함되기 때문에 유망한 노드가 아니어서 백트래킹을 수행하여 상위 노드인 (1, 1) 지점으로 이동한다.
5) 다시 DFS 를 수행하여 다음 노드인 (2, 3) 로 이동한다.
6) (2, 3) 노드를 검사해보니 첫번째 퀸의 이동반경에 포함되지 않아서 유망한 노드가 되었다. 이제 (2, 3) 을 기준으로 DFS 를 수행하여 3번째 퀸의 위치를 찾는다.
이렇듯 가지치기를 통해서 해당 노드가 유망하지 않으면 가차없이 짤라버려서 탐색하는 경로를 최소한으로 줄일 수 있게 된다.
그래서 백트래킹이 뭔데?
간단하게 정리하자면,
Backtracking(백트래킹)
- 완전탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략
- 대표적인 예 : 재귀 호출 or 스택을 통한 DFS이다.
백트래킹의 원리
1) 어떤 노드의 유망성을 점건한 후
2) 유망하지 않으면 배제시킨다. (이러한 행위를 '가지치기'라고 한다.)
3) 해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. (풀이시간이 단축된다.)
N-Queens 구현과 백트래킹
- 헬퍼함수를 어떤 식으로 이용하여 '특정 조건(유망성)'을 따질 것인가??
- n개만큼의 rooks 혹은 queens가 존재하는가?
- 충돌이 존재하지 않는가?
- 조건에 부합하지 않는 경우는 어떤 식으로 넘어갈 것인가?
- 위 조건을 충족하지 않는다면, 다음 row로 넘어가서 탐색을 진행하자.
유망성과 가지치기
- 유망성(Promising) : 가망이 있는가 없는가를 따지는 기준이다.
- 가지치기(Pruning) : 유망성을 따져보고, 유망하지 않는 경우의 수는 배제하는 것이다. ('불필요한 부분을 쳐낸다'라고 보면 된다.)
정리하자면
- 결국, 백트래킹은 스택을 이용한 DFS이다.
- DFS로 진행을 하다 유망하지 않으면 가지치기를 한다.
- 가지치기를 했을 경우, 부모 노드로 돌아간 후
- 다른 자손 노드를 대상으로 DFS를 이용하여 다시 검색한다.
참고자료
'알고리즘 > 알고리즘 종류 설명' 카테고리의 다른 글
| 완전 탐색이란 무엇인가? (0) | 2021.08.18 |
|---|---|
| Dijkstra 알고리즘이란 무엇인가? (0) | 2021.08.15 |
| Floyd 알고리즘이란 무엇인가? (0) | 2021.08.14 |
| DP란 무엇인가? (0) | 2021.08.04 |
| DFS, BFS란 무엇인가? (0) | 2021.07.29 |
댓글