백준 15656번 : N과 M (7) (C 언어)

https://www.acmicpc.net/problem/15656

15656번: N과 M (7)

Code:

#include <stdio.h>
#include <stdlib.h>
 
int n, m;
int arr[9];
int result[9] = { 0, };
 
int compare(const void* a, const void* b)
{
    if (*(int*)a > *(int*)b) return 1;
    else if (*(int*)a < *(int*)b) return -1;
    else return 0;
}
 
void DFS(int count)
{
    if (count == m)
    {
        for (int i = 0; i < m; i++)
        {
            printf("%d ", result[i]);
        }
        printf("\n");
        return;
    }
    int tmp = -1;
    for (int i = 0; i < n; i++)
    {
        if (tmp != arr[i])
        {
            tmp = arr[i];
            result[count] = arr[i];
            DFS(count + 1);
        }
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    qsort(arr, n, sizeof(int), compare);
    DFS(0);
    return 0;
}

문제 설명

주어진 N개의 자연수와 원하는 수열의 길이 M이 주어졌을 때, 중복을 허용하여 M개를 골라 만들 수 있는 모든 수열을 사전 순으로 출력하는 프로그램을 작성해야 합니다. 각 수열은 공백으로 구분되어 출력되며, 중복된 수열은 출력되지 않아야 합니다.

알고리즘 설명

이 문제를 해결하기 위해 사용한 알고리즘은 **깊이 우선 탐색 (DFS)**입니다. 먼저 입력받은 자연수를 오름차순으로 정렬합니다. 그 후, DFS를 통해 모든 가능한 수열을 생성하고 출력합니다. 중복된 수열은 생성되지 않도록 중복을 허용한 조합을 생성하면서 중복을 방지합니다.

프로그램 동작

1. 입력으로 주어진 N개의 자연수를 오름차순으로 정렬합니다.
2. DFS 함수를 호출하여 수열을 생성합니다.
3. DFS 함수에서는 수열의 길이가 M에 도달하면 해당 수열을 출력하고, 도달하지 않으면 가능한 모든 조합을 생성합니다. 중복된 수열을 방지하기 위해 같은 수를 여러 번 고를 수 있으나, 이미 고른 수는 다시 고르지 않도록 합니다.