[c 알고리즘] 1169 정올 주사위 던지기 1 문제 해설

출처:http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=449&sca=2080

[정올 1169 주사위 던지기 1 문제]

언제나 문제가 주어지면 자신의 방식대로 문제를 다시 한 번 정리할 필요가 있다. 

 

문제에서는 주사위를 N번 던진다고했지만, 2번만 던졌을 때를 가정해보겠다.

 

그렇게 되면 2중 for문으로 문제를 해결할 수 있겠지만, N의 범위가 최대 5번이기 때문에 이렇게 되면 for문을 5번 반복해야한다. 

 

이렇게 같은 행위를 여러번 반복할 때 재귀함수를 설계하여 DFS 방법을 사용하면 코드도 깔끔하고 향후 다른 문제에서 응용력도 커진다. 

 

M = 1, M = 2, M = 3일 때 3가지로 분류되기 때문에 solve함수에서 switch case문을 사용해보았다. 

 

이처럼 case가 명확하고 3개 이하일 때는 switch case문을 사용하면 코드도 깔끔하게 정리 된다. 

 

DFS를 구현할 때는 depth를 어떤것으로 할지 정하는게 중요하다. 이번 문제는 주사위를 던진 횟수(N)를 depth로 설정했다.

 

따라서 내가 던진 횟수(n)이 초기 설정했던 N보다 커지면 모든 탐색이 끝났다고 보고 DFS함수를 빠져나오는 것이다.

 

아래 코드를 천천히 읽어보면서 어떻게 설계해나갈지 생각해보는게 중요하다.

 

#include <stdio.h>
int N;//던진횟수
int M;//출력모양
int num[10];
int chk[10];
 
void InputData(void) {
    scanf("%d %d", &N, &M);
}
 
void disp(void)
{
    for (int i = 1; i <= N; i++)
    {
        printf("%d ", num[i]);
    }
    printf("\n");
}
 
void DFS1(int n)
{
    // 중복 순열
    // 1번 주사위 부터 시작하여 N번 주사위까지던지기
    // depth 정하기
    if (n > N)
    {
        disp();
        return;
    }
 
    for (int i = 1; i <= 6; i++)
    {
        num[n] = i;
        DFS1(n + 1);
    }
}
 
void DFS2(int s, int n)
{
    // 주사위를 N번 던져 중복 제외하고 나올 수 있는 모든 경우
    if (n > N)
    {
        disp();
        return;
    }
 
    for (int i = s; i <= 6; i++)
    {
        num[n] = i;
        DFS2(i, n + 1);
    }
 
}
 
void DFS3(int n)
{
    if (n > N)
    {
        disp();
        return;
    }
 
    for (int i = 1; i <= 6; i++)
    {
        if (chk[i] == 1) continue;
        chk[i] = 1;
        num[n] = i;
        DFS3(n + 1);
        chk[i] = 0;
    }
}
 
void solve()
{
    switch (M)
    {
    case 1:
        DFS1(1);
        break;
 
    case 2: 
        DFS2(1, 1);
        break;
 
    case 3: 
        DFS3(1);
        break;
    }
}
 
int main(void) {
    InputData();//입력
 
    solve();
 
    return 0;
}