백트레킹이란? 특정 노드의 유망성(Promising)을 검사하고 유망하다면 자식 노드로, 유망하지 않다면 그 다음 부모 노드로 탐색을 하는 것이다.
N-Queen은 N*N개의 체스판에서 N개의 Queen이 서로 열, 행, 대각으로 겹치지 않는 경우의 수를 구하는 것이다.
첫 번째 부모(첫 번째 행)는 1~n까지의 열을 가질 수 있고
두 번째 부모(두 번째 행)은 1~n까지의 열을 가질 수 있고 -> point
세 번째 부모(세 번째 행)은 1~n까지의 열을 가질 수 있고
.
.
.
N 번째 부모(N번째 행)은 1~n까지의 열을 가질 수 있다.
즉 ,배열로 이용하면
a0 a1 a2 .......... an-1 -> 열
[0] [1] [2] .............[n-1] -> 행
로 표현할 수 있다.(1차원 배열로 나타낼 수 있다!!!!!)
point로 1~N의 행을 만들고 그 안에서 1~N의 열을 반복하여 유망성(Promising)을 검사해본다.
1~point 행까지의 유망성을 검사하면 되므로 배열 값이 같은지(열이 같은지) 비교하고, / 윗방향, \ 윗방향 검사만 해주면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; class Solution { static int[][] maps; static int answer; static int n,queenNum; public static void main(String[] args) throws FileNotFoundException { //Scanner sc = new Scanner(System.in); Scanner sc = new Scanner(new FileInputStream("C:\\Users\\SeonMi\\Desktop\\JavaTools\\Tools\\workspace\\SamsungGoGo\\sample_input.txt")); int T = sc.nextInt(); for(int t=1;t<=T;t++){ answer = 0; n=sc.nextInt(); int[] q = new int[n]; for(int i=0;i<n;i++){ q[0]=i; dfs(q,0); } System.out.println("#"+t+" "+answer); } } private static void dfs(int[] q, int prev) { if(prev+1==n){ answer++; return; } for(int i=0;i<n;i++){ q[prev+1]=i; if(isSatisfied(q,prev+1)) dfs(q, prev+1); // 백트레킹 q[prev+1]=0; } } private static boolean isSatisfied(int[] q, int currCount) { for(int i=0;i<currCount;i++){ if(q[currCount] == q[i]) return false; // 같은 열에 있는지 검사 if(currCount-i == q[currCount]-q[i]) return false; // / 검사 if(currCount-i == q[i]-q[currCount]) return false; // \ 검사 } return true; } } | cs |
'공부 > Algorithm' 카테고리의 다른 글
[백준 알고리즘 - 백트래킹] 스도쿠 (0) | 2017.10.18 |
---|---|
비트마스크 사용해보기 (Java) (0) | 2017.10.17 |
[삼성 SW EA - dfs] 보호필름 (0) | 2017.10.17 |
[삼성 SW EA] 미생물 격리 (다시 풀 것) (0) | 2017.10.09 |
[삼성 SW EA] 점심 식사시간 (다시 풀 것) (0) | 2017.10.07 |