순열 구하기(DFS, 재귀)

문제설명

10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

입력 설명

• 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
• 두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.
  
  

출력 설명

• 첫 번째 줄에 결과를 출력합니다.
• 출력순서는 사전순으로 오름차순으로 출력합니다.

입력예제

3 2
3 6 9

출력예제

3 6
3 9
6 3
6 9
9 3
9 6

내 코드

import java.util.Scanner;

public class Main_8_6 {
    static int n;
    static int m;
    static int[] arr, result, ch;

    void dfs(int lv){
        if(lv == m){
            for(int x : result) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i = 0; i <n; i++){
                if(ch[i] == 0){
                    ch[i] = 1;
                    result[lv] = arr[i];
                    dfs(lv+1);
                    ch[i] = 0;
                }
            }
        }
    }


    public static void main(String[] args) {
        Main_8_6 t = new Main_8_6();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = kb.nextInt();
        }
        result = new int[m];
        ch = new int[n];
        t.dfs(0);


    }
}

• DFS를 활용하여 풀어보았다.
• lv를 통해 정답을 출력하는 result 배열의 인덱스를 정하였고 ch배열을 통해 0이라면 arr[i]의 값을 result에 넣어주었다.
• 재귀를 돌고 다시 돌아올 때 ch배열의 값을 0으로 초기화하여 다시 사용할 수 있도록 하였다.