백준 6603. 로또 :: 돼지개발자

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

"재귀 함수를 활용한 DFS 완전탐색"

해당 문제의 분류는 BFS로 되어있었는데, 흠... DFS가 훨씬 풀기 쉬운 것 같다.

먼저 주어진 숫자 k 중에서 6개를 뽑는 경우의 수를 사전순으로 출력하는 것이다.  따라서 완전 탐색을 해주면 되겠다.

여기서 한가지 팁은 k 가 8일 때 가장 앞에 올 수 있는 배열의 index는 무엇일까... 당연히 0,1,2 가 되겠다. 따라서 dfs 시작 for문에서

[0,k-8) 까지만 검색 하면되겠다... 백트래킹 과정에서 어랏... 앞에 지나온 집합 원소들이 찍히질 않아서 당황했지만,

for문을 돌아 방문한 배열들을 다시 탐색해 그냥 찍어주었따.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
 
    static int k;
    static int[] list;
    static boolean[] visited;
    static StringBuffer sb = new StringBuffer();
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());
            if(k == 0) break;
            
            list = new int[k];
            visited = new boolean[k];
            
            for (int i = 0; i < k; i++) {
                list[i] = Integer.parseInt(st.nextToken());
            }
            
            for (int i = 0; i <= k-6; i++) {
                visited[i] = true;
                solve(i,1);
                visited[i] = false;
            }
            
            sb.append("\n");
        }
        System.out.print(sb.toString());
        
    }
 
    static void solve(int cur, int cnt) {
        
        if(cnt == 6) {
            for (int i = 0; i < k; i++) {
                if(visited[i]) 
                    sb.append(list[i]+" ");
            }
            sb.append("\n");
            return;
        }
        
        for (int i = cur; i < k; i++) {
            if(visited[i]) continue;
            
            visited[i] = true;
            solve(i, cnt+1);
            visited[i] = false;
        }
    }
    
}