0x0C - Backtracking

백트래킹?

--> 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

void funcRecursive(int depth, int n, int m)	// 현재 depth개까지 수를 선택
{
	if (depth == m)	// m개를 모두 선택했다면
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; i++)	// 1부터 n까지의 수에대해
	{
		if (bUsed[i] == false)	// 아직 i가 사용되지 않았다면
		{
			arr[depth] = i;			// depth번째 수를 i로 정한다
			bUsed[i] = true;	// i는 사용했다고 명시
			funcRecursive(depth + 1, n, m);	// 다음 수를 정하러 한 단계 더 들어간다
			bUsed[i] = false;	// depth번째 수를 i로 정한 모든 경우에 대해 다 확인하면 i를 다시 미사용으로 
		}
	}
}

 

 

** N과 M 시리즈의 문제 중에서 1,2,5,6번은 next_permutation을 써서 다시 한번 풀어볼 것

3,4,7,8 같은 문제들은 같은 수를 여러 번 쓸 수 있기때문에 사용하기가 어렵다 **

 

# n개의 수에서 m개를 선택할 때

vector<int> v(n);
for (int i = m; i < n; i++)
{
	v[i] = 1;
}
do
{
	for (int i = 0; i < n; i++)
	{
		if (v[i] == 0)
		{
			// ~~
		}
	}
} while (next_permutation(v.begin(), v.end()));

vector<int> v;
for (int i = 0; i < n; i++)
{
	v.push_back(i < m ? 0 : 1);
}
do
{
	for (int i = 0; i < n; i++)
	{
		if (v[i] == 0)
		{
			// ~~
		}
	}
} while (next_permutation(v.begin(), v.end()));

bool bMask[n] = {};
fill(bMask + m, bMask + n, true);
do
{
	for (int i = 0; i < n; i++)
	{
		if (!bMask[i])
		{
			// ~~
		}
	}
} while (next_permutation(bMask, bMask + n));

// int arr[n] = {1, 2, 3, ~ ,n};
do
{
	reverse(arr + m, arr + n);
	for (int i = 0; i < m; i++)
	{
		cout << arr[i];
	}
} while (next_permutation(arr, arr + n));

 

---

# 출처

https://blog.encrypted.gg/category/%EA%B0%95%EC%A2%8C/%EC%8B%A4%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98