[DFS] 6. 순열 구하기

<<풀이>>

순열 : 서로 다른 n 개 중 r개를 골라 순서를 정해 나열하는 가짓수

 

흔히 우리는 이를 nPr 이렇게 해서 풀어 왔었다. 이를 코드로 하면 아래와 같은 코드로 되는데

이때 DFS를 이용해서 구하면 구현이 가능하다.

 

이전 부터 해오던 ch를 통해 중복되는 경우는 제외시켜준다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

class Main {
    static int n, m;
    static int[] brr, answer, ch;

    private void DFS(int L) {
        if (L == m) {
            for(int x : answer) {
                System.out.print(x + " ");
            }
            System.out.println();
        } else {
            for(int a : brr) {
                if (ch[a] == 0) {
                    ch[a] = 1;
                    answer[L] = a;
                    DFS(L + 1);
                    ch[a] = 0;
                }
            }
        }

    }

    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        n = Integer.parseInt(arr[0]);
        m = Integer.parseInt(arr[1]);

        brr = Arrays.asList(br.readLine().split(" "))
                .stream()
                .mapToInt(Integer::parseInt)
                .toArray();
        answer = new int[m];
        ch = new int[100];
        T.DFS(0);
    }
}