알고리즘/완전탐색(BFS,DFS)

BOJ - 6603 ) 로또 JAVA

개발자가될수있을까? 2020. 1. 23. 15:55

https://www.acmicpc.net/problem/6603

 

6603번: 로또

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2

www.acmicpc.net

숫자를 배열에 담아 

 

6개의 숫자를 DFS로 탐색하면서 방문처리를 통하여 경우의 수를 구한다.

 

 

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
52
53
54
 
import java.lang.reflect.Array;
import java.util.Scanner;
 
public class Main {
    static int num[];
    static int size =6;
    static boolean visit[];
    static ArrayList<Integer> al = new ArrayList<>();
    public static void DFS(int start_index) {
        
        if(al.size() == size) {
            
            for(int index = 0 ; index < size; index++) {
                System.out.print(al.get(index)+ " ");
            }
            System.out.println();
            return;
        }
        for(; start_index <num.length;start_index++) {
            if(!visit[start_index]) {
                visit[start_index] = true;
                al.add(num[start_index]);
                DFS(start_index+1);
                visit[start_index] = false;
                al.remove(al.size()-1);
            }
        }
        
        
        
    }
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        while(len !=0 && len >0) {
            num = new int[len];
            visit = new boolean[len];
            for(int index  = 0 ; index < len ; index++) {
                num[index] = sc.nextInt();
            }
            DFS(0);
            System.out.println();
            len = sc.nextInt();
        }
        
        
        
        
    }
 
}