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

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

---

---

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

---

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());
    }
}
 

예를 들어 입력 값으로 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