문제

이해

전체 수열에서 M개로 이루어진 부분 수열을 모두 출력하는 문제이다.

접근

N개의 수열에서 M개를 뽑아서 만들 수 있는 수열을 출력해야 하는데 수학적으로는 그냥 순열의 경우를 구하면 된다.

하지만 문제의 조건으로 수열은 사전순으로 증가하는 순서로 출력해야 한다.

따라서, 우선 프로그래밍적으로 오름차순으로 N개의 수열을 정렬해야 한다.

순서를 뽑는 방법으로는 백트래킹을 사용하면 된다. 첫번째 수로는 수열의 모든 수가 올 수 있다. 하지만 다음으로 선택될 수는 이전에 선택된 수를 제외해야 한다. 이 조건이 가지치기의 조건이 된다.

백트래킹의 재귀 중단의 조건은 M개의 수를 모두 나열한 경우이다. M개를 모두 뽑으면 재귀를 중단하고 결과를 출력한다.

코드

package java_baekjoon;

import java.util.*;

public class prob15654 {
    static int N;
    static int M;
    static boolean[] visited;
    static int[] arr;
    static int[] selected_arr;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        visited = new boolean[N];
        arr = new int[N];
        selected_arr = new int[M];

        for(int i=0;i<N;i++){
            arr[i] = sc.nextInt();    
        }
        Arrays.sort(arr);

        dfs(0);
    }
    static void dfs(int depth){
        if(depth == M){
            for(int i=0;i<M;i++){
                System.out.print(selected_arr[i] + " ");
            }
            System.out.println();

            return;
        }

        for(int i=0;i<N;i++){
            if(visited[i]){
                continue;
            }

            visited[i] = true;
            selected_arr[depth] = arr[i];
            dfs(depth + 1);
            visited[i] = false;  
        }
    }

    static void selection_sort(int[] arr){
        for(int i=0;i<arr.length;i++){
            int min = i;

            for(int j=i+1;j<arr.length;j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            swap(arr, i, min);
        }
    }

    static void swap(int[] arr, int n, int m){
        int tmp = arr[n];
        arr[n] = arr[m];
        arr[m] = tmp;
    }
}

정렬을 하는 방식에서 시간초과가 발생했다. 최초에는 단순선택정렬로 정렬했다. 왜냐하면 N이 최대 8밖에 되지 않기 때문에 굳이 퀵정렬을 사용할 필요가 없어보였다.

하지만 단순선택정렬을 사용했더니 시간초과가 발생하여 퀵정렬로 바꾸니 정답처리되었다.

원래는 이 문제를 dfs로 풀었다. dfs와 백트래킹이 같은 의미인줄 알았는데 찾아보니 명확하게 구분하고 있었다.

dfs는 트리의 끝까지 탐색하는 방법이고 백트래킹은 탐색 중에 현재 가지가 결과로 유망하지 않으면 탐색을 중단하고 돌아가는 방법이라고 하는데 조금 헷갈린다.

이 부분은 조금 더 조사할 예정이다.

결과