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

문제 링크 : https://www.acmicpc.net/problem/6603

---

이 문제는 백트래킹으로 접근 하면 되는 문제다.

백트래킹은 모든 경우의 수를  탐색을 진행 할때 탐색을 한 후에 다시 값을 탐색하기 이전으로 되돌리는 형태의 알고리즘 이다. 

이 문제는 그럼 어떻게 접근을 해야 할까? 

주어진 k 개의 원소 중에서 하나씩 뽑아서 로또 번호를 생성하면 된다. 

한번 로또 번호에 사용된 원소는 다시 사용 될 수 없기 때문에

i 번째 원소가 로또 번호로 생성 됐다면 그 다음 로또번호는 i+1 부터  k-1 번 째 원소가  될 수 있다. 

예를 들어 k 는 7 이고 원소들의 집합으로 {1, 2, 3, 4, 5, 6, 7} 을 입력 받은 상태에서

{ 1, 2, 3} 까지 로또 번호를 생성 했다면 그 다음 로또 번호로 주어 질 수 있는 원소들은 {4, 5, 6, 7} 이 된다는 말이다. 

그리고 로또 번호의 집합은 항상 오름차순으로 진행 되기 때문에 {1, 2, 4} 의 원소들이 로또 번호로 생성 됐을 때 {3} 은 다음 로또 번호로 추출 될 수 없다. 나머지 {5, 6, 7} 만 다음 로또 번호로 추출 될 수 있다. 

public static void backtracking(int idx, int cnt, String str) {

if(idx >= arr.length ||  idx + MAX - cnt > arr.length) return;

if(cnt == MAX) {

sb.append(str + "\n");

return;

}

for(int i=idx+1; i < arr.length; i++) {

if(visited[i]) continue;

visited[i] = true;

backtracking(i, cnt+1, str + arr[i] + " ");

visited[i] = false;

}

}

이러한 방식으로 백트래킹 소스를 작성 하였다. 

추출된 로또 번호 원소의 수가 6개를 도달 했을때 생성된 로또 번호 문장을 출력해주면 된다.  (cnt == MAX)

소스

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static final int MAX = 6;
    public static int[] arr;
    public static boolean[] visited;
    
    public static StringBuilder sb;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = null;
        
        sb = new StringBuilder();
        while(true) {
            st = new StringTokenizer(br.readLine());
            
            int numCnt = Integer.parseInt(st.nextToken());
            
            if(numCnt == 0) break;
            
            arr = new int[numCnt];
            visited = new boolean[numCnt];
            
            int idx = 0;
            while(idx < arr.length) {
                arr[idx++] = Integer.parseInt(st.nextToken());
            }
            
            for(int i=0; i < arr.length; i++) {
                if(i + MAX > arr.length) continue;
                visited[i] = true;
                backtracking(i, 1, arr[i] + " ");
                visited[i] = false;
            }
            
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public static void backtracking(int idx, int cnt, String str) {
        if(idx >= arr.length ||  idx + MAX - cnt > arr.length) return;
        if(cnt == MAX) {
            sb.append(str + "\n");
            return;
        }
        
        for(int i=idx+1; i < arr.length; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            backtracking(i, cnt+1, str + arr[i] + " ");
            visited[i] = false;
        }
    }
}