[C언어] 백준 15650 : N과 M (2)

https://velog.io/@seochan99/15650-N%EA%B3%BC-M-2 이번에도 이 사람 도움을받았다.. 이 4가지 유형을 알아두고 그때그때 계속 꺼내서보자.

재귀문제를 좀 찾아서 풀어봐야겠다.

풀이

#include <stdio.h>

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

void DFS(int depth, int cut)
{
    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 && cut < i)
            {
                result[depth] = i;
                check[i] = 1;
                DFS(depth + 1, i);
                check[i] = 0;
            }
        }
    }
}

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

15649 문제는 중복되는 수까지 출력해주게 했는데 이는 DFS가 도는데 두번째 for문에서 i가 항상 1부터 시작하기 때문이다 !
왜냐하면 i =2일때 DFS(1)을 시작하면 (2,1)도 출력하게 되면 앞서 출력된 (1,2)와 겹치게 되는데 이때 cut이라는 변수를 넣어서 i가 1보다 클때 실행되게 만들면 되는것이다..!
거기에 check를 제외한 수도 출력하면된다..! 그럼 끗 ..!