[백준] 6603번 : 로또

6603번: 로또

---

[DFS + 백트래킹]

K개의 수를 저장한 배열 arr에 대하여 백트래킹 DFS를 수행한다.

총 K번 반복문을 도는 루프에서 각 시작 정점을 arr[i]번으로 하고, depth가 5가 되면 출력을 위한 버퍼에 현재 방문한 정점들을 담는다.

 

백트래킹을 하기 위해 DFS 내에서 방문 -> DFS 탐색 -> 방문 취소 가 이뤄져야 한다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int k;
    static int[] arr = new int[14];
    static boolean[] visit = new boolean[14];
    static StringBuilder sb;

    static void DFS(int cur, int depth){

        if(depth == 5){
            for(int i=0; i<k; i++)
                if(visit[i])
                    sb.append(arr[i]).append(' ');

            sb.append('\n');
            return;
        }

        for(int i=cur; i<k; i++)
            if(!visit[i]) {
                visit[i] = true;
                DFS(i, depth + 1);
                visit[i] = false;
            }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            sb = new StringBuilder();

            k = Integer.parseInt(st.nextToken());

            if(k == 0) break;

            for(int i=0; i<k; i++)
                arr[i] = Integer.parseInt(st.nextToken());

            for(int i=0; i<k; i++) {
                visit[i] = true;
                DFS(i, 0);
                visit[i] = false;
            }

            System.out.println(sb);
        }
    }
}