중복순열 구하기(DFS, 재귀)

문제설명

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

입력 설명

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

출력 설명

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

입력예제

3 2

출력예제 1

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

---

내 코드

import java.util.Scanner;

public class Main_8_4 {
    static int n;
    static int m;
    static int[] arr;

    void dfs(int lv){
        if(lv == m){
            for(int x : arr){
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i = 1; i <= n; i++){
                arr[lv] = i;
                dfs(lv+1);
            }
        }

    }

    public static void main(String[] args) {

        Main_8_4 t = new Main_8_4();

        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();

        arr = new int[m];
        t.dfs(0);
    }
}

• 출력을 위해 입력 값 m 크기의 arr 배열을 생성하고 재귀를 이용하여 arr[0]에 값이 바뀔 때(?)마다 arr[1]에 1부터 n까지 숫자가 들어가게 반복해주었다.

알게된 점

• 재귀함수에 for문을 활용하는 법을 더 공부해야 할 것 같다!