백준 15649 - N과 M(1)

문제 설명

백트래킹과 관련된 기초 문제이다. 
본인은 백트레킹의 개념은 알지만 코드로 구현함에 있어 어려움을 겪어, 다른 사람들의 코드를 보며 썼다. 

길이가 M이므로, cnt가 M이 될때까지 해당 Backtracking 함수를 실행하게 된다. 
함수를 실행하며, visited를 true로 바꿔주고, 모든 작업을 끝낸 후엔 visited를 false로 바꾼다. 

그 이후 다음 부분을 확인하며, 똑같은 작업을 반복하게 된다. 

현재도 머릿속으로는 이해되었지만, 개념이 정확히 확립이 안된 상태이다. 

좀더 깊게 공부를 해야함을 느낀다. 

 

#include <iostream>
using namespace std;



int N, M;
int arr[10]; //sequence
bool visited[10];//promising

void func(int cnt)//cnt로 현재 몇개를 뽑았는지 count
{
	if (cnt == M)//cnt가 M개(수열의 길이를 만족하면)
	{
		for (int i = 0; i < M; i++) //수열의 길이만큼 출력
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= N; i++) //1부터 N까지 탐색
		if (!visited[i]) //해당 열을 방문한 경우 
		{
			visited[i] = true;//해당 열 유망하게 만들고
			arr[cnt] = i;//수열에 해당 값을 삽입
			func(cnt + 1);
			visited[i] = false;//돌아오고나서 다시 FALSE로 바꿔준다. 
		}
}

int main(void)
{
	cin >> N >> M;

	func(0);
	return 0;
}