[C++] BOJ15649 (back tracking)

[Settpark]

• 그래프의 DFS의 개념을 포함하는 듯 하다.
• 게임의 선택지에서 선택하고 진행하다가 잘못됨을 감지하면 선택하는 부분을 다시 로드해서 게임을 또 진행하는 그런 느낌!

주석을 달아놓은 코드를 보면서 이해하는 게 가장 빠를 듯!

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[10]; //선택한 숫자를 담을 배열
bool isused[10]; // 탐색했는지 확인할 배열

void func(int k) {
	if(k == m) { //base condition
		for(int i = 0 ; i<m; i++) {
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for(int i = 1; i<=n; i++) {
		if(!isused[i]) { // arr[i]를 순서대로 채우다가 채워지지 않은 부분이 발견되었을 때,
			arr[k] = i; // i의 값, 처음에 n으로 입력한 limit값에 기반하여 For문으로 넣음
			isused[i] = 1; // 사용했다는 표시를 해줌
			func(k+1); // 계속 파고 들어가면서 모두 탐색하고 함수 빠져 나오면 
			isused[i] = 0; //이슈의 [i]를 false 해줌, 새로 넣기 위해
			//k+1 .. k+1.. 들어갈 때마다 isused를 true하고 false하고를 반복할 거임.
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	func(0);
}