[C언어] 백준 15654 ~ 15657 : N과 M (5) ~ (8)

9230 단어 C백준백트래킹C

생각의 흐름

아 이제야 좀 보인다...
전에 재귀를 좀 사용해보고 재귀적 생각을 하는 연습을 좀 하니 이제야 좀 보인다.
주요 논리는 N과 M (1)과 같다. 먼저 크기가 각각 다른 숫자가 주어진다.
좀 편하게 하기 위해, 퀵정렬을 사용해서 정렬을 시켜주었고, 그걸 arr배열에 담았다.

그리고 백트래킹함수를 만들어서, 순열인지 체크(자기 자신이 나오면 안된다.)를 한다. 그걸 test[i]로 만들어두었고, 정렬을 사용한 arr배열을 print배열에 depth를 설정해주어 넣어주었다.
// 여기까지 N과 M (5) 설명이다.
6, 7, 8은 방금 해보니 (2), (3), (4)와 거의 동일하다. 끝.

#include <stdio.h>
#include <stdlib.h>

int n, m;
int arr[10];
int test[10];
int print[10];

int compare(const void *a, const void *b)
{
    int num1 = *(int *)a;
    int num2 = *(int *)b;
    if (num1 < num2)
        return -1;

    if (num1 > num2)
        return 1;

    return 0;
}

void bt(int depth)
{
	int i;
	if (m == depth)
	{
		i = 0;
		while (i < m)
		{
			printf("%d ",print[i]);
			i++;
		}
		printf("\n");
	}
	else
	{
		i = 0;
		while (i < n)
		{
			if (test[i] == 0)
			{
				test[i] = 1;
				print[depth] = arr[i];
				bt(depth + 1);
				test[i] = 0;
			}
			i++;
		}
	}
}

int main()
{
	int i;
	scanf("%d %d", &n, &m);
	i = 0;
	while(i < n)
	{
		scanf("%d", &arr[i]);
		i++;
	}
	qsort(arr, n, sizeof(int), compare);
	bt(0);
}

좋은 웹페이지 즐겨찾기