[백준 N과 M(1)] 백트래킹 문제

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

15649번: N과 M (1)

배운점 : 

1. BackTracking 문제는 깊어진 depth 에서 다시 빠져나올 때도 생각해야한다.

DFS 시행 후 다시 visited, arr 업데이트

2. 중복검사는 visited[i]로 하는게 빠르다. ( 다이나믹 프로그래밍) for문으로 일일이 중복되는지 확인하지 말자.

 

3. 코딩하면서 변수가 코드로써 뭘 의미하는지도 적어놓고 하면 생각이 편하다.

ex) depth는 tree의 깊이(개념)이자 arr의 인덱스 역할(코드로써의 의미)로 썼다.

   i는 해당 depth에서 넣을 number의 의미로 사용됐다.

 

 

#include <iostream>

using namespace std;

#define MAX 9

int visited[MAX];
int arr[MAX];
int N, M;
//int cnt;
void DFS(int depth)
{
	if (depth >= M)	// finish condition
	{
		for (int i = 0; i < M; i++)
		{
			cout << arr[i] << " ";

		}
		cout << "\n";
		//cnt++;
		return;
	}
	// NOT finish condition
	else
	{
		for (int i = 1; i <= N; i++) // i : number, depth : index
		{
			if (!visited[i])
			{
				visited[i] = 1;
				arr[depth] = i;
				DFS(depth + 1);
				visited[i] = 0;
				arr[depth] = 0;
			}
		}
	}
}

int main()
{
	cin >> N >> M;
	DFS(0);
	//cout << cnt;
	
	return 0;
}