[BOJ] 백준 6603 - 로또 (자바)

백트래킹..  비트연산..

나는 비트연산으로 한번 풀고 백트래킹으로 한번 풀었다.

근데 이 문제처럼 사전순으로 정렬해서 출력해야 한다는 가정이 나와있는 문제는 백트래킹이 훨씬 풀기 쉬운거 같다.

백트래킹의 경우 순차적으로 접근하기 때문

두 문제 똑같이 result[] 배열와 arr[] 배열을 사용했다.

result[] 배열의 경우, 갯수 6개가 되는 경우의 수를 파악하기 위해 이용된다. ( 배열 안에는 0과 1 로 구성되어있다.)

arr[] 배열의 경우, 출력할 때 필요한 값들을 가지고 있다. 출력할 때 값이 손상되면 안되므로 result[] 배열을 사용했다.

풀이

1. result[] 배열을 통해 경우의 수를 구한다. (4자리라면 0000 부터 1111까지 모든 수를 구한다.)

2. 모든 수중에 1의 개수가 원하는 개수(로또 문제에서는 6개) 일 때 출력한다.

3. 개수를 체크하는 방법은 비트연산에서는 count 변수를 사용했고, 백트래킹 같은 경우 함수를 들어갈때 depth 인자로 사용했다.

4. 출력시에 result[] 배열이 1인 부분만 출력하되 출력은 arr[] 배열을 출력한다.

끝

비트연산시에 result[] 배열은 사전순으로 출력해야 되기 때문에 반대로 저장해야한다.

소스

(비트연산)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            String[] str = br.readLine().split(" ");
            int N = Integer.parseInt(str[0]);
            int[] arr = new int[N];
            int[] result = new int[N];
 
            if (N == 0) {
                break;
            }
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(str[i + 1]);
            }
 
            for (int i = (1<<N)-1; i >=0; i--) {
                Arrays.fill(result, 0);
                int count = 0;
                int bit = i;
                for (int j = 0; bit != 0; j++, bit >>= 1) {
                    if ((1 & bit) == 0) {
                        continue;
                    }
                    // 사전순 정렬을 해야하기 때문에 반대로 출력해줘야한다.
                    result[Math.abs((N-1)-j)] = 1;
                    count++;
                }
                if (count == 6) {
                    for (int k = 0; k <N; k++) {
                        if(result[k]==1)
                        System.out.print(arr[k] + " ");
                    }
                    System.out.println();
                }
            }
            System.out.println();
        }
 
    }
 
}

(DFS 백트래킹)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
class Main {
    static int N;
    static int[] arr;
    static int[] result;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            String[] str = br.readLine().split(" ");
            N = Integer.parseInt(str[0]);
            arr = new int[N];
            result = new int[N];
 
            if (N == 0) {
                break;
            }
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(str[i + 1]);
            }
            DFS(0,0);
            System.out.println();
        }
 
 
    }
    public static void DFS(int start, int depth){
        if(depth==6){
            print();
        }
        for(int i=start; i<N; i++){
        result[i] = 1;
        DFS(i+1,depth+1);
        result[i] = 0;
        }
        
    }
    public static void print(){
        for(int i=0; i<N; i++){
            if(result[i]==1)
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    
}