[Algorithm] 순열 구하기, 중복순열 구하기(DFS)

순열이란

서로다른 n개 원소중 r개를 선택하여 일렬로 나열하는 경우의 수를 말한다.

 

예를들어 A/B/C/D 4개 중 3개의 원소를 뽑았다면 선택된 원소는 ABC ACD ABD BCD 4가지가 된다.

이렇게 위치와 순서 상관없이 단순하게 뽑아낸 것을 조합이라고 하는데

여기서 원소들의 순서와 위치를 다르게 하여 일렬로 나열 하는 것을 순열이라고 한다.

즉 순열은 위치와 순서가 있는 조합이다.

 

위의 4가지 조합 중에 하나인 ABC를 위치와 순서에 따라 나열하는 경우

ABC ACB BAC BCA CAB CBA - 6가지의 경우의 수가 생긴다.

 

즉 ABC의 경우의 수 6

ACD 의 경우의 수 6

BCD 의 경우의 수 6

ABD의 경우의 수 6

이렇게 해서 A/B/C/D 4개 중 3개의 원소를 뽑는 순열의 경우의 수는

6 + 6 + 6 + 6 = 24개가 된다.

 

그러므로

4P3= 24이 된다.

 

문제로 바로 만나보자.

 

---

 

설명

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

 

풀이.

public class Main {
    static int n;
    static int m;
    static int[] arr; // 실제 주어진 자연수 값 배열
    
    // n개의 자연수 크기의 배열
    // 0 또는 1로 입력받은 자연수 값을 사용 했는지 안했는지 여부로 사용 할것 (중복방지)
    static int[] ch;
    
    // level을 index로 사용하여 해당 level에서 구한 값을 넣어주게 할것 (위치와 순서)
    // ex) 출력 시 3 6과 6 3
    static int[] pm; 

    static void DFS(int level){
        if(level == m){
            for(int x : pm) System.out.printf(x+" ");
            System.out.println();
            return;
        }else{
            for (int i = 0; i < n; i++) {
                if(ch[i] == 0){
                    ch[i] = 1;
                    pm[level] = arr[i];
                    DFS(level+1);
                    ch[i] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n];
        ch = new int[n];
        pm = new int[m];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        DFS(0);
    }
}

 

 

 

---

 

중복순열이란

순열에서 중복까지 허용하는 경우의 수를 중복순열 이라고 한다.

예를들어 위 순열에서 AAB AAC AAA BBB ... 이런식으로 중복까지 허용한 경우의 수를 말한다.

 

문제로 바로 만나보자.

 

---

 

설명

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열
하는 방법을 모두 출력합니다.

 

입력

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

 

출력

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

 

예시 입력 / 출력

3 2	1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3

 

풀이.

public class Main {
    static int n; // 1부터 n까지의 양수
    static int m; // m번 뽑는다. -> level0과 level1에서 만들고 level2에서 출력
    static int[] arr; // m크기의 배열
    
    static void DFS(int level) {
        if(level == m){
            for(int x : arr) System.out.printf(x+" ");
            System.out.println();
            return;
        }else{
            for (int i = 1; i <= n; i++) {
                arr[level] = i;
                DFS(level+1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[m];
        DFS(0);
    }
}

 

---

 

정리 :

DFS(0)을 시작으로!

입력받은 자연수 arr 배열

순열일 경우 중복을 방지하기 위해 체크여부를 0또는 1로 넣어줄 입력받은 자연수 크기의 ch배열과

순열의 위치와 순서를 알맞은 index에 넣어주기 위해 해당 DFS(level) 매개변수를 index로 활용!