백준 - 6603 로또(Java)

dfs 문제입니다.

 

dfs를 사용하여 주어진 집합 S에서 순열을 만들고 앞에서 부터 6자리를 선택하되, 해당 자리가 모두 오름차순일 경우에만 정답에 추가하면 됩니다.

 

[구현 코드]

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static final int LENGTH = 6;

    private static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        while (true){
            stz = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(stz.nextToken());

            if(n == 0) break;

            int[] arr = new int[n];
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(stz.nextToken());
            }

            permutation(arr, arr.length, 0);
            answer.append(System.lineSeparator());
        }

        bw.write(answer.toString());

        bw.flush();
        bw.close();
        br.close();
    }

    private static void permutation(int[] arr, int n, int depth) {
        if(depth == LENGTH){ // 순열이 다 만들어졌을 때
            StringBuilder sb = new StringBuilder();
            for(int i=1; i<LENGTH; i++){
                if(arr[i] < arr[i-1]) return; // 오름차순이 아니면 해당 탐색 종료
                sb.append(arr[i-1]).append(" ");
            }
            sb.append(arr[LENGTH-1]);
            answer.append(sb).append(System.lineSeparator());
            return;
        }

        for(int i=depth; i<n; i++){
            swap(arr, depth, i);
            permutation(arr, n, depth+1);
            swap(arr, depth, i);
        }
    }

    private static void swap(int[] arr, int i, int depth){
        int tmp = arr[i];
        arr[i] = arr[depth];
        arr[depth] = tmp;
    }
}