'알고리즘&자료구조/백트랙킹'에 해당되는 글 2건

  1. 2018.03.16 :: 백트랙킹- N-QUEEN(백준 9663번)
  2. 2018.03.16 :: 백트랙킹-로또문제(백준 6603번)

1. 백트래킹을 이용한 N-QUEEN 문제 (백준 9663번)






2.백트랙킹을 이용한 풀이



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
package recursiveandbacktracking;
import java.util.Scanner;
 
public class Baekjun9663BacktrackingNQueen {
    static int[] iArr;
    static int count;
    static int N;
    
    //퀸이 놓일수 있는가?
    static boolean promising(int[] iArr,int N,int row) {
        for(int i=0;i<row;i++) {
            if(iArr[row]==iArr[i] || row-i==Math.abs(iArr[row]-iArr[i])) {
                return false;
            }
        }
        return true;
    }
    static void nQueen(int[] iArr,int N,int row) {
         for(int i=0;i<N;i++) {
             iArr[row]=i;
             //퀸이 놓일수 있다면? 다음 행에 대해 퀸을 놓는다. 혹은 마지막 행이면 count수를 증가시켜준다.
             if(promising(iArr, N, row)) {
                 if(row==N-1) count++;
                 else {
                     nQueen(iArr, N, row+1);
                 }
             }
         }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        iArr=new int[N];
        nQueen(iArr, N, 0);
        System.out.println(count);
    }
}
 
cs



4X4 체스판에서의 예를 들어보면 처음에 nQueen(iArr,4,0) 이라는 함수를 호출한다. 이 함수의 뜻은 1번째 행에 퀸을 놓는다 라는 뜻이다. 함수 속에 들어가게 되면 1번째 행에는 퀸을 1,2,3,4 열에 퀸을 놓을 수 있다. 이것을 각각의 경우로 따지기 위해 for문의 인덱스를 0<=i<N 이라는 값으로 셋팅 해준것이다. 그리고 iArr[0]=0 이 들어가게 된다. 이 뜻은 1번째 행의 1번째 열에 퀸을 놓겠다 라는 뜻이다. 그런다음 조건문안에 promising(iArr,4,0) 이라는 함수를 호출하게 된다. 이 함수 안에 들어가게 되면 지금 행의 이전까지의 퀸을 놓은 경우에 따라 지금 놓은 퀸의 위치가 유효한가를 따져보는 함수이다. 하지만 row가 0이므로 이전의 놓은 값은 아무것도 없기에(i<0) for문 자체를 돌지 않으므로 return 값은 true가 되어 퀸을 놓을 수 있게 된다. 여기서 promising 함수안의 조건문을 보면 iArr[row]==iArr[i] || row-i==Math.abs(iArr[row]-iArr[i]) 이라는 조건이 있다.

이 조건은 퀸의 성질을 나타낸 것인데 퀸은 자신이 놓인 곳에서 행,열, 대각선 아무 곳이나 이동하여 공격 할수 있다라는 성질을 이용해 만약 이전에 놓였던

퀸들의 위치에서 행,열,대각선 위치와 지금 놓은 퀸의 위치가 같다면 false를 리턴하라는 조건문이다. 이렇게 row를 하나씩 증가시켜가며 퀸을 놓는 것이다.

만약 promising이 false라면 다음 퀸을 놓지 않고 for문으로 다시 돌아가 i를 1 증가시켜 다음 위치에 퀸을 놓았을때를 비교 한다.(백트랙킹) 만약 해당 열에

어느곳에도 놓을수 없다면 이전 퀸으로 돌아가 이전 퀸의 위치를 i+1로 변경해서 다시 퀸을 놓는 경우의 수를 따져보는 것이다.(백트랙킹)


입력:

8

출력:

92


'알고리즘&자료구조 > 백트랙킹' 카테고리의 다른 글

백트랙킹-로또문제(백준 6603번)  (0) 2018.03.16
posted by 여성게
:

1.백트랙킹- 로또문제(백준6603번)






2. 백트랙킹을 이용한 풀이


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
package recursiveandbacktracking;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class Baekjun6603BacktrackingLotto {
    static int K;
    static int[] iArr;
    static int count;
    static StringBuffer sb=new StringBuffer();
    static void dfsForRecursive(int v,String str) {
        if(count==6) {
            sb.append(str+"\n");
        }else {
            for(int i=v+1;i<K;i++) {
                ++count;
                dfsForRecursive(i, str+iArr[i]+" ");
            }
        }
        --count;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        
        while((K=sc.nextInt())!=0) {
            iArr=new int[K];
            for(int i=0;i<K;i++) {
                iArr[i]=sc.nextInt();
            }
            for(int i=0;i<K;i++) {
                count=1;
                dfsForRecursive(i,iArr[i]+" ");
            }
            
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}
 
cs



예를 들어 입력 값으로 1 2 3 4 5 6 7 이 들어왔다고 가정해보자. 그러면 반복문 안에서 count=1 되면서 dfsForRecursive(0,1+" "); 함수 안에 들어가게 된다. 그런 다음에 count가 6이 아니므로 for문으로 들어가게 된다. 이제 dfsForRecursive함수 안에는 iArr[0](v=0) 보다는 큰수의 인덱스로 함수에 들어가게 된다. 이런 식으로 쭉쭉 가다보면 처음으로 StringBuffer에 들어가는 수는 1 2 3 4 5 6 이라는 값이 된다. 그러면 else 밑에 count가 -1되고 함수가 리턴이 된다. 이 함수는 for문 안에서 호출한 dfsForRecursive(5,1 2 3 4 5 +iArr[5]+" ") 이다. 이 함수가 리턴이 된다면 for문의 다음 인덱스 i=6 값으로 함수의 매개변수로 들어간다. dfsForRecursive(6,1 2 3 4 5 +iArr[6]+" ") 이값도 count가 6이 됬음으로 StringBuffer에 append 시켜주고 함수가 끝나게 된다. 그렇다면 더 이상 돌 for의 인덱스가 없으므로 이전의 함수 dfsForRecursive(4,1 2 3 4 +iArr[4]+" ") 함수가 끝나게 되고 다음 dfsForRecursive(5, 1 2 3 4 +iArr[5]+" ")를 호출하게 되는 것이다. 이런 식으로 main 함수 안의 for문이 끝날때까지 반복되게 된다. 그런데 여기서 주의 해야할 점은 dfsForRecursive 함수 안의 for문의 시작인덱스가 v+1이라는 것이다. 왜 자신보다 큰 값을 들어오게 하는 것일까? 이것의 예를 들자면 예를 들어서 값이

1 2 3 4 5 6 , 1 2 3 4 5 7 이라는 결과로 함수가 끝났다고 생각하자 그 다음은 1 2 3 4 6 ? 로 시작을 하게 될 것이다. 여기서 v+1이라는 값이 발휘 한다. 만약 1 2 3 4 6 5 라는 값이 들어오게 되면? 이 문제는 중복을 허락하지 않음으로 바로 위의 1 2 3 4 5 6 이라는 값과 중복이 되버린다. 그래서 v+1을 함으로써 이전에 나왔던 결과값과 중복이 되지 않게 하는 것이다.


입력:

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0


출력:

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34


'알고리즘&자료구조 > 백트랙킹' 카테고리의 다른 글

백트랙킹- N-QUEEN(백준 9663번)  (0) 2018.03.16
posted by 여성게
: