문제

코드

#include <stdio.h>

int n,m;
int result[1000];
int check[1000];

void DFS(int depth)
{
    int i;
    
    if(depth==m)
    {
        for(int i=0;i<m;i++)
            printf("%d ",result[i]);
        printf("\n");
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            if(check[i]==0)
            {
                result[depth]=i;
                check[i]=1;
                DFS(depth+1);
                check[i]=0;
            }
        }
    }
}

int main(void)
{
    scanf("%d %d",&n,&m);
    DFS(0);
    return 0;
}

해설

DFS로 접근하면 되는 백트레킹 문제이다.
수학적으로 본다면 순열문제라고 보면된다...!
nPm 의 순열을 구해야하는 것인데 이것을 DFS로 구현했다
checklist라는 배열을 두고 중복된 값이 출력되는것을 조건문으로 막아줬다
DFS를 구현할때 재귀함수의 개념만 잘 이해하고있으면 되는 그러한 문제이다 !

실행구조

N=4, M=2 이고,
depth = 0,i=1일때
1. DFS[0]-> result[0]=1 -> check[1]=1 -> DFS(1)
2. DFS[1]-> (i=2일때)result[1]=2 -> check[2]=1 -> DFS(2)
3. DFS[2] -> (1,2) 출력
-> 2번으로 돌아가서 체크 초기화하고 i++ 해서(1,3),(1,4)출력
-> 1번으로 돌아가서 체크 초기화 하고 i++해서 같은 방식으로 (2,1),(2,3),(2,4) 출력..
반복 !!!

재귀는,,..! 매력적이다.!