[Algorithm]알고리즘 자바_57 중복 순열 구하기(DFS)

 

💬 문제 설명

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

 

✨ 아이디어

​

m번의 뽑기로 뽑을 수 있는 한번의 경우의 수를 PM에 저장하자 (pm[m]).

기존의 유무를 검사하는 문제들과는 다르게(이진 트리), 1~N까지의 가능성을 모두 조사한다.

 

• 재귀 탈출 조건
  
  • 최대 레벨에 도달하면 return

 

💻 Solution.java

import java.util.*;

public class Main {
	static int[] pm;
	static int n, m;
	public void DFS(int L) {
		if(L == m) {
			for(int i = 0; i < m; i++) {
				System.out.print(pm[i] + " ");
			}
			System.out.println();
		}
		else {
			for(int i = 1; i <= n; i++) {
				pm[L] = i;
				DFS(L + 1);
			}
		}
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); // 번호
		m = sc.nextInt(); // 뽑을 갯수
		
		pm = new int[m];
		main.DFS(0);
		
		sc.close();
		return ;
	}
}