백트래킹
- 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾는 알고리즘
- DFS는 가능한 모든 경로를 탐색하지만 백트래킹은 해를 찾아가는 도중 경로가 해가 될 거 같지 않으면 그 경로를 더 이상 찾아가지 않고 되돌아 간다.
- 가지치기 - 불필요한 부분을 쳐내고 최대한 올바른 쪽을 간다
백트래킹은 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 탐색하는 것이다.
해가 될 만한지 판단 후 유망하지 않으면 가지치기 후 이전(부모) 노드로 돌아간다.
N-Queen
public class NQueen{
static int N = 4;
static int[][] board = new int[4][4];
public static void main(String[] args){
if(put_queen(0) == false){
System.out.println("Solution does not exist!");
} else {
for(int i=0; i < N; i++){
for(int j=0; j < N; j++){
System.out.print(board[i][j] + ", ");
}
System.out.println();
}
}
}
// 재귀와 반복을 통해 문제를 해결하는 메소드(각 컬럼에 대해 체크)
private static boolean put_queen(int col){
// N보다 열의 숫자가 높거나 같다면 모든 열에 퀸이 배치된 상태를 의미
if(col >= N) return true;
// 현재 열(Column)에서 각 행을 하나씩 체크한다.
for(int i=0; i < N; i++){
// 현재 열의 i번째 행에 퀸을 위치시킬 수 있는지 파악
if(check(i, col) == true){
board[i][col] = 1;
// 위치 시켰으면, 이후 열에 대해서도 연속적으로 가능한지 확인!
if(put_queen(col+1) == true){
return true;
}
// 만약 이후 열에 대해서 true 반환이 안되었다면 다시 0으로 수행하고
// 백트래킹을 통해 다음 row로 넘어가서 수행
board[i][col] = 0;
}
}
// true를 이전에 반환 못했다면 답이 없는 것이므로 false 반환
return false;
}
// 현재 행/열에 퀸이 이미 배치된 상태인지 확인하는 메소드
private static boolean check(int row, int col){
int i,j;
// 현재 행의 모든 열에 퀸이 있는지 테스트
for(i = 0; i < col; i++){
if(board[row][i] == 1){
return false;
}
}
// 현재 위치의 좌상단 대각선으로 퀸이 있는지 테스트
for(i = row, j = col; i >= 0 && j >= 0; i--, j--){
if(board[i][j] == 1){
return false;
}
}
// 현재 위치의 우하단 대각선으로 퀸이 있는지 테스트
for(i = row, j = col; i < N && j >= 0; i++, j--){
if(board[i][j] == 1){
return false;
}
}
return true;
}
}
'코딩테스트 > [알고리즘] 알고리즘 정리' 카테고리의 다른 글
이진 탐색 알고리즘 (0) | 2021.10.07 |
---|---|
다이나믹 프로그래밍 (0) | 2021.10.05 |
그리디 알고리즘 (0) | 2021.10.04 |
그래프 탐색 알고리즘 - DFS / BFS (0) | 2021.10.02 |
최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜) (0) | 2021.10.01 |