[백준] 6603번 - 로또 (Java)

 

<문제해석>

1. 줄의 첫 숫자가 N이고, 뒤부터 로또에 사용될 정수들이 배열이 입력된다.

2. 중복방문을 허용하지 않는다. (방문배열 사용)

3. 순서가 바꾸어도 동일 조합으로 인정한다. (i=start부터 시작)

4. 종료조건은 level == N이다.

 

<코드구현 #1>

import java.util.Scanner;
import java.util.Arrays;
import java.lang.StringBuilder;
import java.util.HashSet;

public class Main {
    static int N, S;
    static int sum = 0, count = 0;
    static int A[];
    static int Ans[];
    static boolean visited[];

    void DFS(int start, int level) {
        // 종료 조건
        // tree level이 6만큼 진행되면 종료
        if (level == 6) {
            for (int x : Ans) {
                System.out.print(x+" ");
            }
            System.out.println();
            return;
        }
        // 재귀호출 조건
        for (int i=start; i<N; i++) {
            if (visited[i]) continue;
            Ans[level] = A[i];
            visited[i] = true;
            DFS(i, level+1);
            visited[i] = false;
        }
    }
    
    void Solve() {
        DFS(0, 0);
        System.out.println();
    }
 
    public static void main(String[] args) {
        Main m = new Main();
        Scanner sc = new Scanner(System.in);
        while (true) {
            N = sc.nextInt();
            if (N == 0) break;

            A = new int[N];
            visited = new boolean[N];
            Ans = new int[6];
            for (int i=0; i<N; i++) {
                A[i] = sc.nextInt();
            }
            m.Solve();
        }
    }
}