주사위 던지기1(DFS)

문제 설명

---

주사위를 던진 횟수 N과 출력형식 M을 입력 받아서 M의 값에 따라 각각 아래와 같이 출력하는 프로그램을 작성하시오.
M = 1 : 주사위를 N번 던져서 나올 수 있는 모든 경우
M = 2 : 주사위를 N번 던져서 중복이 되는 경우를 제외하고 나올 수 있는 모든 경우
M = 3 : 주사위를 N번 던져서 모두 다른 수가 나올 수 있는 모든 경우

• 중복의 예
  1 1 2 와 중복 : 1 2 1, 2 1 1
  1 2 3 과 중복 : 1 3 2, 2 1 3, 2 3 1, 3 1 2

입력 설명

---

첫 줄에 주사위를 던진 횟수 N(2≤N≤5)과 출력모양 M(1≤M≤3)이 들어온다.

출력 설명

---

주사위를 던진 횟수 N에 대한 출력모양을 출력한다.
작은 숫자부터 출력한다.

입력 예시

---

3 1

출력 예시

---

1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 2 1
…
6 6 6

#include <stdio.h>
int N;//던진횟수
int M;//출력모양
 
int num[10];
void DFS1(int n){//중복순열
    if (n >= N){//종료조건, N회 주사위 덧졌음
        for (int i=0; i<N; i++){
            printf("%d ", num[i]);
        }
        printf("\n");
        return;
    }
    for (int i=1; i<=6; i++){
        num[n]=i;
        DFS1(n+1);
    }
}
void DFS2(int n, int s){//중복조합
    if (n >= N){//종료조건, N회 주사위 덧졌음
        for (int i=0; i<N; i++){
            printf("%d ", num[i]);
        }
        printf("\n");
        return;
    }
    for (int i=s; i<=6; i++){
        num[n]=i;
        DFS2(n+1, i);
    }
}
 
int used[10];//사용 표시용
void DFS3(int n){//순열
    if (n >= N){//종료조건, N회 주사위 덧졌음
        for (int i=0; i<N; i++){
            printf("%d ", num[i]);
        }
        printf("\n");
        return;
    }
    for (int i=1; i<=6; i++){
        if (used[i]) continue;//i 숫자 사용 중
        used[i]=1;//사용으로 표시
        num[n]=i;
        DFS3(n+1);
        used[i]=0;//표시제거
    }
}
 
void Solve(void){
    if (M == 1){//중복순열
        /*for (int a=1; a<=6; a++){
            for (int b=1; b<=6; b++){
                for (int c=1; c<=6; c++){
                    printf("%d %d %d\n", a, b, c);
                }
            }
        }*/
        DFS1(0);//던진 횟수
    }
    else if(M == 2){//중복조합
        /*for (int a=1; a<=6; a++){
            for (int b=a; b<=6; b++){
                for (int c=b; c<=6; c++){
                    printf("%d %d %d\n", a, b, c);
                }
            }
        }*/
        DFS2(0, 1);//던진 횟수, 시작 숫자
    }
    else{//M==3, 순열
        DFS3(0);//던진 횟수
    }
}
 
void InputData(void){
    scanf("%d %d", &N, &M);
}
 
int main(void){
    InputData();//입력
 
    Solve();//여기서부터 작성
 
    return 0;
}