[C언어] 백준 15663 ~ 15666 : N과 M (9) ~ (12)

9668 단어 C백준백트래킹C

생각의 흐름

그냥 뚝딱뚝딱 풀었다. 근데 처음에 오답이 되었는데, 예제를 보면 알겠지만 같은값이 두번 나오면 안된다. 그래서 조건에 print[depth] != arr[i] 를 추가해서 했는데, 예제는 다 맞지만 3 3 , 1 1 2를 넣어보면 2줄밖에 출력되지 않는다.
디버깅해보니 1 1 2, 1 2 1까지는 잘 출력이 되지만, 2 1 1까지 저장을 하지만 1 1이 같은값으로 bt함수에 들어가지 못한다(print[depth]는 현재값이다.)
그렇기에 value를 만들어서, 직전값을 저장해준다음에 arr[i]와 비교하는 방식으로 진행했다.

나머지 3개도 동일하다.

#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;
	int value = -1;
	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 && value != arr[i])
			{
				value = arr[i];
				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);
}

좋은 웹페이지 즐겨찾기