BOJ - 6603

1. 문제

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

2. 풀이

백트래킹을 적용하는 문제로 집합 S에서 로또 번호가 될 6개의 번호를 고르면 되기 때문에 재귀를 활용하여 문제를 풀면 된다. 로또 번호는 정렬되어 오름차순으로 주어지고 로또 번호를 하나 선택하였다면 그 번호는 다시 들어가지 않아야 하기에 index를 이용하여 그 번호 다음부터 탐색을 이어나가면 된다.

import java.util.*;
import java.io.*;

public class Main6603 {
    static int k;
    static int [] s;
    static StringBuilder sb;
    static boolean [] visited;
    static void rec(int count, int index){
        if(count == 6){
            for(int i = 0; i < k; i++){
                if(visited[i])
                    sb.append(s[i]).append(" ");
            }
            sb.append('\n');
            return;
        }
        else{
            for(int i = index; i < k; i++){
                if(!visited[i]){
                    visited[i] = true;
                    rec(count+1, i+1);
                    visited[i] = false;
                }
            }
        }
    }
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();
        while(true){

            k = sc.nextInt();
            if(k == 0) {
                sb.delete(sb.length()-2, sb.length());
                break;
            }
            s = new int[k];
            visited = new boolean[k];
            for(int i = 0; i < k; i++){
                s[i] = sc.nextInt();
            }
            rec(0, 0);
            sb.append('\n');
        }
        System.out.print(sb.toString());
    }
}

3. 적용된 알고리즘

재귀, 백트래킹