[백준] 6603 로또 - 백트래킹 JAVA

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

6603번: 로또

코드설명

백트래킹 문제입니다.

 

문제로직입니다.

1. 주어진 집합 S를 모두 입력받습니다.
2. 집합 S중에서 6가지만 뽑으면 되므로, level == 6 일때 중단시키도록 처리합니다.
   1. 이때, level이 올라가는 과정에 idx를 활용하여 해당 자리에서 선택된 수열의 원소 뒤의 원소들만 넣을 수 있도록 처리하여 오름차순으로 정렬하고, 반복된 숫자를 넣지 않도록 설정했습니다.

 

코드

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

public class Main {
	
	public static int k, S;
	public static int answer = 0;
	public static int[] arr;
	public static boolean[] visited;
	public static int[] answerArr;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	answerArr = new int[6];
    	while(true) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		k = Integer.parseInt(st.nextToken());
    		if(k == 0) 
    			break;
    		
    		arr = new int[k];
    		visited = new boolean[k];
    		for(int i=0;i<k;i++) {
    			arr[i] = Integer.parseInt(st.nextToken());
    		}
    		
    		simulate(0, 0);
    		System.out.println();

    	}
    }
    
    public static void simulate(int idx, int level) {
    	if(level == 6) {
    		for(int i=0;i<6;i++) {
    			System.out.print(answerArr[i]+" ");
    		}
    		System.out.println();
    		return ;
    	}
    	for(int i=idx;i<k;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			answerArr[level] = arr[i];
    			simulate(i+1, level + 1);
    			visited[i] = false;
    		}
    		
    	}
    	
    }
    
}