[Ch.08 - DFS] 08. 순열 구하기

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

 

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

 

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

 

입력예제 1 

3 2
3 6 9

 

출력예제 1

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

 

---

문제 풀이 순서

1. N개의 자연수 -> M개를 뽑아 나열
2. ds
   1. 값을 저장하는 리스트
      • 자연수 n개 중 저장 
   2. 중복확인 리스트
      • n개의 중복확인
   3. 순열을 일렬로 배열하는 리스트
      • m개를 뽑는다.
3. L==m이 되면
   1. 저장된 배열을 출력
4. 그 외에는 L==m이 될때 까지 
   1. 자연수 n개만큼 반복하는데
   2. 중복체크 하면서 값 배열에서 가져오기
   3. 사용하기 전 체크리스트에 1로 변경
   4. 값 배열에서 가져와 결과 배열에 넣기
   5. 기준 값 다음 값 가져오기
   6. 사용 후 체크리스트 0으로 초기화 

 

---

import java.util.Scanner;
//순열 구하기 [중복 제외]
//N개의 자연수 중 M개를 뽑아 중복 없이 일렬로 나열
//사전순으로 오름차순

class Main {
	static int n, m, answer;
	static int[] pm, ch, arr;
	// pm: 결과 배열, ch : 중복 체크 배열, arr : 값 배열

	public void DFS(int L) {
		// 3 2-> 3 6 9 -> 3 6, 3 9, 6 3, 6 9, 9 3, 9 6
		if (L == m) {
			// 한 개의 순열 완성
			for (int x : pm) {
				System.out.print(x + " ");
			}
			System.out.println();
		} else {
			for (int i = 0; i < n; i++) {
				if (ch[i] == 0) {
					// 중복체크 하면서 값 배열에서 가져오기
					ch[i] = 1;
					// 사용하기 전 체크리스트에 1로 변경
					pm[L] = arr[i];
					// 값 배열에서 가져와 결과 배열에 넣기
					DFS(L + 1);
					// 기준 값 다음 값 가져오기
					ch[i] = 0;
					// 사용 후 체크리스트 0으로 초기화
				}
			}
		}
	}
	public static void main(String[] args) {
		Main T = new Main();
		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();
		}
		ch = new int[n];
		pm = new int[m];
		T.DFS(0);

	}
}