[PS] 인프런 강의 - DFS 4. 중복순열 구하기

 

문제

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

 

풀이

헛다리 짚어서 BFS로 풀다가 때려쳤긴한데 될 것같긴한데....

암튼 DFS로 풀면 되는데 다소 헷갈릴 수 있는 문제다. 스택 프레임을 그리면서 순서를 따라가보는 것을 추천한다.

 

중복순열의 경우의수를 저장할 길이 m의 배열 pm을 선언한다.

 

예제에서는 구슬을 m=2번 뽑으니까 다음과 같다.

 

[L=0]

[L=1]

 

예제에서는  [L=0] 자리에 1, 2, 3이 들어갈 경우의 수, [L=1] 자리에 1, 2, 3이 들어갈 경우의 수가 있는데 서로 곱하면 9가지 경우가 나온다. 

 

DFS 함수에 L=0 파라미터를 넣고 시작해서,

[L=0]에 들어갈 수 있는 i = { 1, 2 , 3} 를 순회하며 pm[L] 배열에 값을 넣고 DFS(L+1) 재귀호출을 한다.

 

 

 

재귀 호출 되는 과정은 다음과 같다.

 

• D(0) i=1
  • →  D(1) i=1 → D(2) 출력: "1 1" 
  • 복귀→ D(1) i=2 → D(2) 출력: "1 2"
  • 복귀→ D(1) i=3 → D(2) 출력: "1 3"
• 복귀→  D(0) i=2
  • → D(1) i=1 → D(2) 출력: "2 1"
  • ... 반복

 

코드

import java.util.Scanner;

public class Main {
	
	static int[] pm; //뽑은 구슬 저장할 배열
	static int n, m;
	
	//L = 레벨 = 뽑은 구슬 인덱스 = pm의 인덱스 순회
	public static void DFS(int L) {
		if(L == m) {
			for(int x : pm) System.out.print(x + " ");
			System.out.println();
		}
		else {
			//구슬 n개 순회
			for(int i=1; i<=n; i++) {
				pm[L] = i;
				DFS(L+1); //레벨+1;
			}
		}
	}

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        n = in.nextInt(); //3~10
        m = in.nextInt();//2~n
        pm = new int[n-1];
        
        //n개의 구슬을 m번 뽑아서 나열(중복 가능)
        DFS(0); //pm의 0번 인덱스부터 저장
        
    }
}