[알고리즘] 백준 6603번 로또 Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int k;
    static int [] s;
    static boolean [] chk;
    public static void main(String[] args) throws  Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            String testCase=br.readLine();
            if(testCase.equals("0")) break;
            String [] input=testCase.split(" ");
            k=Integer.parseInt(input[0]);
            s=new int[k];
            chk=new boolean[k];
            for(int i=0;i<k;i++){
                s[i]=Integer.parseInt(input[i+1]);
            } //초기 값 세팅

            dfs(0,0);
            System.out.println();
        }
    }

    public static void dfs(int depth,int start){
        if(depth==6){
            for(int i=0;i<k;i++){
                if(chk[i]){
                    System.out.print(s[i]+" ");
                }
            }
            System.out.println();
        }
        for(int i=start;i<k;i++){
            chk[i]=true;
            dfs(depth+1,i+1);
            chk[i]=false;
        }
    }
}

이번 문제는 재귀함수를 이용하여 백트래킹을 구현해야 한다.

글쓴이의 경우 백트래킹을 잘 몰라서 한 참 해매다가 검색하여 제가 해석하기 쉽게 코드를 바꿔 풀었습니다.. ㅠㅠ 더 열심히 해야겠습니다.

depth를 기준으로 잡고 생각하면 조금 더 이해하기 쉬울거같습니다.

감사합니다.