백준 15649번 N과 M(2)

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

백트래킹 단계별로 풀기 첫번째 문제이다.

백트래킹 -> 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아가는 것

내 알고리즘

재귀함수를 통해 반복문을 동적으로 처리

Test함수를 통해 추가되는 수가 이미 array에 있으면 제외

내 코드

#include <stdio.h>

int array[8];

int Test(int M)
{
	int i, temp;
	temp = array[M];//새로 추가되는 수를 temp라 하자.
	for (i = 0; i < M; i++)
	{
		if (temp == array[i]) return 1;//앞에 있는 수와 temp 중 같은게 있으면 1을 return
	}
	return 0;//아니면 0을 return
}

void F(int N, int M, int cur)
{
	int i;
	if (cur == M)//0 ~ M-1까지 배열에 차면 배열 출력
	{
		for (i = 0; i < M; i++)
		{
			printf("%d ", array[i]);
		}
		printf("\n");

		return;
	}
	for (i = 1; i <= N; i++)
	{
		array[cur] = i;
		if (Test(cur)) continue;
		F(N, M, cur + 1);
	}
}



int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	F(N, M, 0);

	return 0;
}

수정한 코드 (1)

함수를 호출하는데 시간이 오래 걸리는 것 같아서
Test함수를 호출하지 않는 코드로 수정

#include <stdio.h>

int array[8];

void F(int N, int M, int cur)
{
	int i , j , k;
	if (cur == M)
	{
		for (i = 0; i < M; i++)
		{
			printf("%d ", array[i]);
		}
		printf("\n");

		return;
	}
	for (i = 1; i <= N; i++)
	{
		k = 0;
		array[cur] = i;
		for (j = 0; j < cur; j++)
		{
			if (array[j] == i) k = 1;
		}
		if (k) continue;
		F(N, M, cur + 1);
	}
}



int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	F(N, M, 0);

	return 0;
}