DFS, BFS 활용 - 순열 구하기

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 {

    static int n;
    static int m;
    static int[] p;
    static int[] ch;

    public static void DFS(int L, int[] a) {
        if (m == L) {
            for (int x : p) {
                System.out.print(x + " ");
            }
            System.out.println();
        } else {
            for (int i = 0; i < n; i++) {
                if (ch[i] == 0) {
                    ch[i] = 1;
                    p[L] = a[i];
                    DFS(L + 1, a);
                    ch[i] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        p = new int[m];
        ch = new int[n];
        DFS(0, a);
    }
}