중복순열 구하기

 

설명

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

 

입력

첫 번째 줄에 자연수 N(3<=C<=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

 

문제 해결

 

이 문제는 N과 M에 대해 중복 순열을 만들어 출력하는 문제이다. 중복 순열은 각 요소가 한 번 이상 선택될 수 있는 순열을 을 말한다. 예를 들어 N이 3이고 M이 2라면, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)와 같이 각 번호가 여러 번 선택될 수 있는 것이다.

 

static int N, M;
static int[] selected;

 

자연수 N과 M에 대해 전역 변수로 선언해주고, 선택된 숫자들을 저장할 selected 배열을 선언해준다.

그 이후  N과 M을 입력받고 selected 배열을 selected = new int[M];

  M으로 초기화해준다.

 

public static void DFS(int L) {
    if (L == M) { // M번 뽑았으면 출력
        for (int num : selected) {
            System.out.print(num + " ");
        }
        System.out.println();
        return;
    }
    for (int i = 1; i <= N; i++) { 
        selected[L] = i; // 현재 깊이에 i를 선택
        DFS(L + 1); // 다음 깊이로 재귀 호출
    }
}

 

DFS 함수이다. 레벨 L이 M과 같으면, 즉 M번을 모두 뽑았다면, selected 배열에 저장된 모든 숫자를 출력한다.

L이 M이 아니면 1부터 N까지 각 숫자를 선택하고, selected[L]에 넣구 DFS 함수를 호출한다.

 

DFS(0);

 

main 에서 DFS(0) 을 호출해 재귀적으로 가능한 순열을 만들고 출력해간다.

 

 

최종 코드

 

import java.util.Scanner;

public class P04_중복순열 {
    static int N, M;
    static int[] selected;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        selected = new int[M];

        DFS(0);
    }

    public static void DFS(int L) {
        if (L == M) { // M번 뽑았으면 출력
            for (int num : selected) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= N; i++) { 
            selected[L] = i; // 현재 깊이에 i를 선택
            DFS(L + 1); // 다음 깊이로 재귀 호출
        }
    }
}