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

04. 중복순열 구하기

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

 

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

 

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

 

입력예제 1 

3 2

 

출력예제 1

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

---

문제 풀이 순서 : 구슬의 개수만큼 반복하는데, 구슬의 개수가 배열의 길이가 된다면, 배열 출력

1. 배열의 길이 n으로 된, 결과배열 선언
2. DFS -> O,X로 나눈다 
3. 중복을 허용해 N개중 M번을 뽑아 모두 나열하기
   
   1. L==m이면, 배열 모두 출력
   2. 그외엔 깊이탐색
      1. 구슬의 개수까지 반복하는데
      2. M개의 배열에 구슬을 뽑은 순서대로 구슬의 번호를 결과배열에 저장
      3. 다음 구슬 뽑기

---

import java.util.Scanner;
//중복 순열
//N까지 번호가 적힌 구슬을 중복 허용해 M번 뽑아 일렬로 나열
//자연수 N과 M
//사전순으로 오름차순 출력

class Main {

	static int n,m;
	static int[] pm;
	
	public void DFS(int L) {
		if(L==m) {
		//구슬의 개수가 M번일 경우	
			for(int x: pm)
			//배열에 있는 모든 숫자 출력
			System.out.println(x+" ");
		}
		else {
			for(int i=1;i<=n;i++) {
			//구슬의 개수까지 반복
				pm[L]=i;
				//M개의 배열에 구슬을 뽑은 순서대로 구슬의 번호 입력
				DFS(L+1);
				//다음 구슬 뽑기
				}
		}
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		pm=new int[m];
		//m개의 배열 생성
		T.DFS(0);
	}
}

 

+) arr를 전역 변수로

import java.util.Scanner;

public class Main {
	static int[] pm;
	static int n, m;

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		pm = new int[m];
		DFS(0);
	}

	static void DFS(int L) {
		if (L == m) {
			for (int x : pm)
				System.out.print(x + " ");
			
			System.out.println();
			return;
		} else {

			for (int i = 1; i <= n; i++) {
				pm[L] = i;
				DFS(L + 1);
			}
		}
	}

}