[21.07.30] 재귀함수, 트리, DAT

------------------------0730-재귀함수
* 
* ------------------체스판 코드 확인하기
#include <iostream>

using namespace std;

char path[10];
char name[5] = "ABCD";
int input;
int s = 0;
char used[4];

void abc(int level) {
	if (level == input) {
		s++;
		return;
	}

	for (int i = 0; i < input; i++) {
		if (used[i] == 1) continue;
		used[i] = 1;
		path[level] = name[i];
		abc(level + 1);
		path[level] = 0;
		used[i] = 0;
	}

}

int main() {

	cin >> input;

	abc(0);

	cout << s;

	return 0;
}
* 
* 
* //이웃해서 같은카드 받지않는 소스 AAA(x) ABA(o) 

#include<iostream>
using namespace std;

char path[10];


void abc(int level) {
	if (level>=2 && path[level - 1] == path[level - 2]) return; //2번방법

	if (level == 3) {
		cout << path << endl;
		return;
	}

	for (int i = 0; i < 4; i++) {
		//if (level>0 && path[level - 1] != i + 'A')) { //1번방법
			path[level] = i + 'A';
			abc(level + 1);
			path[level] = 0;
		//}
	}
}


int main()
{
	abc(0);

	return 0;

}

* 
* 
//B가 들어가는 경우 모두 제외
//1 진입하지 않는경우 2 진입했다가 return

#include<iostream>
using namespace std;

char path[10];


void abc(int level) {
	if (level>0 && path[level - 1] == 'B') return; //2번방법

	if (level == 3) {
		cout << path << endl;
		return;
	}

	for (int i = 0; i < 4; i++) {
		//if (!(i + 'A' == 'B')) { //1번방법
			path[level] = i + 'A';
			abc(level + 1);
			path[level] = 0;
		//}
	}
}


int main()
{
	abc(0);

	return 0;

}
* 
//C로 시작하는 경우 제외
//1 진입하지 않는경우 2 진입했다가 return

#include<iostream>
using namespace std;

char path[10];


void abc(int level) {
	//if (path[0] == 'C') return; //2번방법

	if (level == 3) {
		cout << path << endl;
		return;
	}

	for (int i = 0; i < 4; i++) {
		//if (!(level == 0 && i + 'A' == 'C')) { //1번방법
			path[level] = i + 'A';
			abc(level + 1);
			path[level] = 0;
		//}
	}
}
* -------카드3장뽑기 중복제외 순열
#include<iostream>
using namespace std;

char path[10];
int used[4]; // A B C D 사용됐는지 확인

void abc(int level) {
	if (level == 3) {
		cout << path << endl;
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (used[i] == 1) continue; //다음 반복 실행
		used[i] = 1;
		path[level] = i+ 'A';
		abc(level + 1);
		path[level] = 0;
		used[i] = 0;//출력된 경우 다시 초기화
	}
}


int main()
{
	abc(0);

	return 0;

}
* ------------------5개배열에 OX출력하는 모든 경우의수
//lv :5, br : 2

#include<iostream>
using namespace std;

int n[5] = { 0 };
char path[10];
char name[3] = "OX";

void abc(int level) {
	if (level == 5) {
		cout << path << endl;
		return;
	}

	for (int x = 0; x < 2; x++) {
		path[level] = name[x];
		abc(level + 1);
		path[level] = 0;
		//path[level] = 0;
	}
}

int main()
{
	abc(0);

	return 0;

}
* 
* -------------------주사위 n개 돌렸을때 나올수있는 모든 경우의수
//lv :n, br : 6

#include<iostream>
using namespace std;

int n;
char path[7];
void abc(int level) {
	if (level == n) {
		cout << path <<endl;
		return;
	}

	for (int x = 0; x < 6; x++) {
		path[level] = '1' + x;
		abc(level + 1);
		//path[level] = 0;
	}
}

int main()
{
	cin >> n;
	abc(0);

	return 0;

}
* 
* -----------------ABCD카드더미에서 3가지글자조합 모든경우의수 출력
#include<iostream>
using namespace std;

char path[5];
void abc(int level) {
	if (level == 3) {
		cout << path <<endl;
		return;
	}

	for (int x = 0; x < 4; x++) {
		path[level] = 'A' + x;
		abc(level + 1);
		path[level] = 0;
	}
}

int main()
{
	abc(0);

	return 0;

}
* 
* -------------트리의 가장 하위레벨 출력하기
#include<iostream>
using namespace std;

int path[10];
void abc(int level) {
	if (level == 2) {
		for (int x = 0; x < level; x++) {
			cout << path[x] << " ";
		}

		cout << endl;
		return;
	}

	for (int x = 0; x < 3; x++) {
		path[level] = x + 1;
		abc(level + 1);
		path[level] = 0;
	}
}

int main()
{
	abc(0);

	return 0;

}
* 
* 
* 문자열에 사용된 알파벳 알아보기(중복출력x dat문)
* #include<iostream>
using namespace std;

int de;
int main()
{
    char vect[9] = "ABCQADBC"; 
    
    int flag[100] = { 0 }; 
    for (int i = 0; i < 8; i++) {
        int val = vect[i]; 
        flag[val] = 1;
    }

    for (char target = 'A'; target <= 'Z'; target++) {
        if (flag[target] == 1)
            cout << target;
    }

    return 0;
    
}
* -------------------문자열에 사용된 알파벳 알아보기(중복출력x 이중for문)
* #include<iostream>
using namespace std;

int de;

int main()
{
	char arr[9] = "ABCQADBC";
	char s[8];

	for (char target = 'A'; target <= 'Z'; target++) {
		int flag = 0;
		for (int i = 0; i < 8; i++) {
			if (arr[i] == target) {
				flag = 1;
			}
		}
		if (flag == 1)cout << target;
	}


	return 0;

}
* 
*  ---------------------------배열에 1~9까지 각각 몇개있는지(dat이용)
* #include<iostream>
using namespace std;

// dat이용하기 cnt 변수를 여러개 만들었음
int de;
int arr[8] = { 3,2,1,2,5,3,2,1 }; // 수 0~9

int main()
{
	int cnt[10] = { 0 }; // cnt 변수 10개
	for (int i = 0; i < 8; i++) {
		int val = arr[i];
		cnt[val] ++; // counting 3 2 1 2 5 3 2 1
	}

	for (int val = 0; val < 10; val++) {
		if (cnt[val] != 0) {
			cout << val << " : " << cnt[val] << endl;
		}
	}


	return 0;

}
* 
* ---------------------------배열에 1~9까지 각각 몇개있는지(2중for문)
* #include <iostream>

using namespace std;

int arr[] = { 3,2,1,2,5,3,2,9 };

int main() {
	int c[10] = { 0 };

	for (int target = 0; target < 10; target++) {
		int cnt = 0;
		for (int i = 0; i < 8; i++) {
			if (arr[i] == target) cnt++;
		}
		if (cnt != 0)
			cout << target << " : " << cnt << "개" << "\n";
	}

	return 0;
}
* 
* ----------원하는 순서로 출력하기
#include <iostream>

using namespace std;

int arr[7] = { 3,7,5,9,8,7 };
int order[6] = { 2,3,1,5,-1,4 };

void run(int now) {
	cout << arr[now] << " ";
	if (order[now] == -1) {
		return;
	}
	run(order[now]);

	return;
}

int main() {

	run(0);

	return 0;
}
* 
* 
#include <iostream>

using namespace std;

void abc(int level) {


	if (level == 2) {
		return;
	}

	//abc(level +1);
	//abc(level +1);

	for (int i = 0; i < 2; i++) {
		abc(level + 1);
	}
	int d = 1;
}

int main() {

	abc(0);

	return 0;
}

* 
* 
#include <iostream>

using namespace std;

int n[] = {4,7,9,1,5};

void abc(int x) {

	cout << n[x]<<" ";

	if (x == 4) {
		return;
	}


	abc(x + 1);
	cout << n[x] << " ";

	int d = 1;
}

int main() {

	abc(0);

	return 0;
}

* 
* 
#include <iostream>

using namespace std;

int n;

void abc(int x) {
	cout << x<<" ";

	if (x == 1) {
		return;
	}


	abc(x - 1);
	cout << x << " ";

	int d = 1;
}

int main() {

	cin >> n;
	abc(n);

	return 0;
}
* 
* 
#include <iostream>

using namespace std;

void abc(int x) {
	if (x == 2) {
		return;
	}

	abc(x + 1);

	int d = 1;
}

int main() {

	abc(0);

	return 0;
}

* 
* 
#include <iostream>

using namespace std;
int n;
int path[6];

void abc(int level) {
	if (level == n)
	{
		for (int x = 0; x < level; x++) {
			cout << path[x] << " ";
		}
		cout << endl;
		return;
	}

	for (int x = 1; x <= 6; x++) {
		path[level] = x;
		abc(level + 1);
	}

}

int main() {
	cin >> n;

	abc(0);

	return 0;
}

 

- 체스판 참고

#include<iostream>
using namespace std;

char map[4][5]; // 디버깅용도
int used[4]; // 0 1 2 3 세로 라인사용여부 
int cnt = 0;
int input;

void run(int y) {
	if (y == input) {
		cnt++;
		return;
	}
	for (int x = 0; x < input; x++) {
		if (used[x] == 1) continue;
		used[x] = 1;// 사용함
		map[y][x] = '#';
		run(y + 1);
		map[y][x] = '_';
		used[x] = 0; // 원상복구
	}
}
int main()
{

	cin >> input;
	for (int y = 0; y < 4; y++) { for (int x = 0; x < 4; x++) map[y][x] = '_'; }
	run(0);
	cout << cnt;
	return 0;
}