백 트래킹(BackTracking)
- 백트래킹, 또는 퇴각 검색으로 부른다.
- 제약조건 만족 문제(Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략
: 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack(다시는 이 후보군을 체크하지 않을 것을 표기) 하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법이다.
- 실제 구현 시 고려할 수 있는 모든 경우의 수(후보군) 을 상태 공간트리(State Space Tree) 를 통해 표현한다.
* 상태 공간 트리 : 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리
* 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될 만한 곳으로 바로 넘어가서 탐색한다.
- Promising : 해당 루트가 조건에 맞는지를 검사하는 기법
- Pruning(가지치기) : 조건에 맞지 않으면 포기하고, 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법
-즉, 백 트래킹은 트리 구조를 기반으로 DFS 로 깊이 탐색을 진행하면서, 각 루트에 대해 조건이 부합하는지 체크(Promising), 만약 해당 트리(나무) 에서 조건에 맞지 않는 노드는 더 이상 DFS 로 깊이 탐색을 진행하지 않고 가지를 쳐버린다.(Pruning)-
N Queen 문제
- 대표적인 백트래킹 문제이다.
- NxN 크기의 체스판에 N 개의 퀸을 서로 공격할 수 없도록 배치하는 문제
- 퀸은 다음과 같이 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야 한다.
Pruning (가지치기) for N Queen 문제
- 한 행에는 하나의 퀸 밖에 위치할 수 없다.(퀸은 수평 이동이 가능하므로)
- 맨 위에 있는 행 부터 퀸을 배치하고, 다음 행에 해당 퀸이 이동할 수 없는 위치를 찾아 퀸을 배치한다.
- 만약 앞선 행에 배치한 퀸으로 인해, 다음 행에 남은 퀸 들을 배치할 곳이 없어진 경우(어딜 놔도 이전 행에 있는 퀸과 서로 공격할 수 있게되는 경우) 더 이상 퀸을 배치하지 않고 이전 행의 퀸의 배치를 바꿔준다.
* 즉, 맨위의 행부터 전체 행 까지 퀸의 배치가 가능한 경우의 수를 상태 공간 트리 형태로 만든 후, 각 경우를 맨 위의 행 부터 DFS 방식으로 접근, 해당 경우가 진행이 어려울 경우 더 이상 진행하지 않고 다른 경우를 체크하는 방식이다.
Promising for N Queen 문제
- 해당 루트가 조건에 맞는지를 검사하는 기법을 활용하며, 현재까지 앞선 행에서 배치한 퀸이 이동할 수 없는 위치가 있는지를 다음과 같은 조건으로 확인한다.
* 한 행에 어차피 하나의 퀸만 배치 가능하므로 수평 체크는 별도로 하지 않는다.
자바 코드로 직접 작성해보자.
- NQueen.java
import java.util.ArrayList;
import java.util.List;
public class NQueen {
public static void main(String[] args) {
int n = 4; // 배치해야 하는 퀸의 갯수
// 배치 형태를 리스트 형태로 저장
List<Integer> list = new ArrayList<Integer>();
List<List<Integer>> finalResult = new ArrayList<List<Integer>>();
dfs(n, 0, list, finalResult);
finalResult.stream().forEach(x -> System.out.println(x.toString()));
}
private static void dfs(int n, int currentRow, List<Integer> currentCandidate,
List<List<Integer>> finalResult) {
// currentCandidate : 이전 행에서 퀸 들의 배치 정보
if(currentRow == n) { // 배치가 모두 끝났을 경우
List<Integer> resultList = new ArrayList<Integer>();
for(int i = 0; i < currentCandidate.size(); i++) {
resultList.add(currentCandidate.get(i));
}
finalResult.add(resultList);
}
else { // 배치가 다 끝나지 않았을 경우
// candidateCol : 체크 해야 하는 열의 번호
for(int candidateCol = 0; candidateCol < n; candidateCol++) {
// 조건에 만족하는 열이 있는 경우
if(isAvailable(currentCandidate, candidateCol)) {
currentCandidate.add(candidateCol);
dfs(n, currentRow+1, currentCandidate, finalResult);
// 위의 dfs 재귀 문에서 조건에 만족하는 열을 찾지 못하여
// 그냥 return 을 받았을 경우
// 가장 최근에 배치된 퀸의 정보를 삭제하고,
// 삭제한 해당 행의 퀸 부터 다시 배치를 시작한다.(백트래킹)
// 다음 행에 대한 퀸의 배치가 불가능해 졌으므로,
// 이전 행의 퀸의 위치를 이전과는 다른 곳으로 다시 배치한다.
currentCandidate.remove(currentCandidate.size()-1);
}
}
}
}
// 수직 체크 및 대각선 체크
private static boolean isAvailable(List<Integer> currentCandidate, int candidateCol) {
int currentRow = currentCandidate.size();
for(int queenRow = 0; queenRow < currentRow; queenRow++) {
if(currentCandidate.get(queenRow) == candidateCol ||
Math.abs(currentCandidate.get(queenRow) - candidateCol)
== currentRow - queenRow)
return false;
}
return true;
}
}
'자료구조 및 알고리즘 > 알고리즘' 카테고리의 다른 글
[알고리즘] 자바에서의 최소 신장 트리(프림 알고리즘) (0) | 2021.12.16 |
---|---|
[알고리즘] 자바에서의 최소 신장 트리(크루스칼 알고리즘) (0) | 2021.12.15 |
[알고리즘] 자바에서의 다익스트라 알고리즘(최단 경로 알고리즘) (0) | 2021.12.12 |
[알고리즘] 자바에서의 그리디(탐욕) 알고리즘 (0) | 2021.12.10 |
[알고리즘] 자바에서의 BFS 와 DFS (0) | 2021.12.07 |