N과 M(백트래킹)

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

15649번: N과 M (1)

 재귀함수 호출을 이용한 백트래킹 알고리즘이다.

 

 백트래킹은 모든 경우의 수를 탐색함과 동시에 가망이 없는 경우의 수에 대해선 탐색을 미리 끝내버리는 방법이다.

 

 N과 M 문제는 1~N 범위의 자연수 중 M개의 자연수를 중복없이 고르는 문제다.

 M개의 자연수를 고르기 위해선 중복 for문을 돌린 뒤, 중복되는 수가 없는지 판단하면 되겠지만 N과 M 범위가 커질수록 기하급수적인 연산을 요구하게 될 것이다.

 따라서 첫 번째 자연수부터 두 번째, 세 번째 자연수를 고르는 행위(DFS) 중 중복되는 자연수가 발생하면 그 다음 자리는 탐색하지 않도록 해야한다. 이러한 행위를 백트래킹이라고 한다.

 

 N과 M 문제에서 boolean 리스트를 사용해서 이미 선택한 자연수인지 여부를 판단하여 백트래킹을 구현하도록 한다.

 

#include<iostream>
using namespace std;

int range, seq;
bool check[9] = { 0, };
int ret[9] = { 0, };

void PrintRet()
{
	for (int i = 0; i < seq; i++)
	{
		cout << ret[i] << " ";
	}
	cout << '\n';
}


void DFS(int count)
{
	if (count == seq)
	{
		PrintRet();
		return;
	}
	for (int i = 1; i <= range; i++)
	{
		if (!check[i])
		{
			check[i] = true;
			ret[count] = i;
			DFS(count + 1);
			check[i] = false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> range >> seq;
	DFS(0);
}