728x90
◇ 설명
- 백트래킹을 개선
- 가지뻗기 + 한정 조작( bounding )
※ 한정 조작 : 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법
◇ 코드
ex) N-Queens
Q) 크기가 N*N인 체스판에 N개의 퀸 말을 같은 행, 대각선1, 2 와 겹치지 않게 배치할 수 있는 경우의 수,
각 열에 배치된 말의 행 출력
import java.util.Arrays;
import java.util.Scanner;
public class Main { // 백준 9663번
static boolean[] flag_a, flag_b, flag_c;
static int n, cnt = 0, pos[];
static void set( int i ) {
for( int j = 0; j < n; j++ ) {
if( flag_a[j] == false && flag_b[i+j] == false && flag_c[i-j+(n-1)] == false ) {
pos[i] = j;
if( i == (n-1) ) {
System.out.println( Arrays.toString( pos ) );
cnt++;
}
else {
flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)] = true;
set( i + 1 );
flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)] = false;
}
}
}
}
public static void main(String[] args) {
// 크기가 N*N인 체스판에 N개의 퀸 말을 같은 행, 대각선1, 2 와
// 겹치지 않게 배치할 수 있는 경우의 수, 각 열에 배치된 말의 행 출력
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
sc.close();
flag_a = new boolean[n];
flag_b = new boolean[2*n-1];
flag_c = new boolean[2*n-1];
pos = new int[n];
set(0);
System.out.println(cnt);
}
}
( https://hyunjiishailey.tistory.com/175 )
◇ 출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바
반응형
'컴퓨터 공학 ( Computer Science ) > 알고리즘 ( Algorithm )' 카테고리의 다른 글
[알고리즘] 그래프 탐색 ( Graph Search ) - 깊이 우선(DFS), 너비 우선(BFS ) (0) | 2021.03.20 |
---|---|
[알고리즘] 이분/이진 탐색 ( Binary Search ) (0) | 2021.03.20 |
[알고리즘 기법] 백트래킹 ( 되추적 방법 ) ( Backtracking ) (0) | 2021.03.20 |
[알고리즘 기법] 분할정복법 ( Divide and Conquer ) (0) | 2021.03.20 |
[알고리즘 기법] 동적계획법 ( 다이나믹 프로그래밍 : DP ( Dynamic Programming ) ) (0) | 2021.03.20 |