[인프런] 08_06 순열 구하기(DFS)

📖  문제

---

• 첫 번째 줄에 결과를 출력합니다.
• 출력순서는 사전순으로 오름차순으로 출력합니다.
  • 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어진다.
  • 두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.

출력 예시

 

⚠️  주의사항

---

• 오름차순으로 출력

 

✍️  이해

---

/**
 * 1. 주어진 입력 값들 입력 + check, answer 용 배열 추가
 * 2. line = M -> for-each( i : answer ) sout(i + " ")
 * 3. for(0 ~ N) if check[i] == 0
 * 4. arr의 현재값을 answer[line] 추가
 * 5. DFS 다음 라인 호출
 * 6. check[i] 0으로 초기화
 */

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    static int N, M;
    static int[] arr, check, answer;

    public void DFS(int L) {

        if(L == M) {
            for (int i : answer) System.out.print(i + " ");
            System.out.println();
        }else{
            for (int i = 0; i < N; i++) {
                if (check[i] == 0) {
                    answer[L] = arr[i];
                    DFS(L + 1);
                    check[i] = 0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        arr = new int[N];
        check = new int[N];
        answer = new int[M];

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

        T.DFS(0);
    }
}

---