[C/C++ 8.3] 알고리즘 - 재귀/DFS/BFS

 

 

재귀사용

기본

// Level 21
//3번
void recur(int level, int branch, int LV) {	// level, branch는 입력받은 값  //LV 은 현재 상황
	// level은 트리의 깊이 (몇번이나 재귀 안으로 깊숙히 들어가는가)
	if (LV == level)					
		return;							
	// branch는 가지의 개수 (재귀가 몇번이나 반복되는가 )
	for (int i = 0; i < branch; i++)	
		recur(level,branch,LV + 1);
}
int main() {
	int level, branch;
	cin >> level >> branch;
	// 재귀실행
	recur(level,branch,0);
}

 

Path 추가 

// Level 22
//3번															
int path[10];
char branch[4] = { 'B', 'G', 'T', 'K' };			//문자열은 따로 저장해서
void recur(int LV,int lev) {		// TOP-DOWN
	// level
	if (lev == LV) {
		for (int i = 0; i < LV; i++) {
			cout << branch[path[i]];	// 순서에 따라 문자열 저장해둔거 출력 !
		}
		cout << endl;
		return;
	}
	// branch
	for (int i = 0; i < 4; i++) {
		path[lev] = i;			// path 표시 
		recur(LV,lev + 1);
	}

}
int main() {
	int lv;
	cin >> lv;
	recur(lv, 0);		// 무조건 0 부터 시작해야, TOP-DOWN 구조로 감
	return 0;
}

Path - 사전 순 몇번째인지 Check 

//7번
  //level = 3/ branch =4 ABCD
int path[10];
int cnt = 0;
void recur(string str,int level) {
	//level
	if (level == 3) {							// 몇번째 경우의 수 인지 세는 로직 !!!
		cnt++;									// cnt++ 은 한 단계마다 해주어야 함
        // 입력한 정답 str과 현재경우가 같다면,
		if (str[0] == path[0] && str[1] == path[1] && str[2] == path[2])
			cout<<cnt<<"번째";
		return;
	}
	//branch
	for (int i = 0; i < 4; i++) {
		path[level] = 'A'+i;
		recur(str,level + 1);
	}
}
int main() {
	string str;
	cin >> str;
	recur(str,0);
	return 0;
}

 

 

특정 조건 제외 

// 2번					// 네글자 입력 중, T,B가 연속되는 경우 제외
// level = 4 branch =4						
char path[4];
char input[4];
int cnt = 0;
void recur(int level) {
	//level
	if (level == 4) {
		cnt++;
		//for (int i = 0; i< 4; i++) {
		//	cout << path[i];
		//}
		//cout << endl;
		return;
	}
	//branch
	for (int i = 0; i < 4; i++) {
		// 'B'랑 'T' 가 연속해서 나오면 안됨 !!!
		// level 이 0 보다 커야함 조건 이해 하기 !!
		// 아직 지금은 path 들어가기전이므로, input[i]로 비교해야됨 !!   ******************** 정리
		if ((path[level-1] == 'B' && input[i]=='T' && level>0) || (path[level-1] == 'T' && input[i] == 'B' && level>0)) continue;
		path[level] = input[i];
		recur(level + 1);
	}

}
int main() {
	for (int i = 0; i < 4; i++) {
		cin >> input[i];
	}

	recur(0);
	cout << cnt;
	return 0;
}

 

 

N명 뽑기(중복X) [조합]  *****

//4번
// B T S K R에서 n 명을 순서대로 뽑아 유닛결성, 첫사람 : 리더,  S는 꼭 있어야함 중복 x
// level = n, branch =5
int cnt = 0;
char path[5];
int used[5];
int n;
char member[5] = { 'B','T','S','K','R' };
void recur(int level) {
	// level
	if (level == n) {	// n명 뽑기
		// 'S'군이 있을 때만 숫자 셈
		if(used[2]==1)
			cnt++;
		return;
	}
	//branch
	for (int i = 0; i < 5; i++) {
		if (used[i] == 1) continue;		// 중복 x
		used[i] = 1;
		path[level] = member[i];
		recur(level + 1);
		used[i] = 0;
	}

}
int main() {
	cin >> n;
	recur(0);
	cout << cnt;
	return 0;
}

 

특정 조건이 되는 경우의 수 

 n 개중 4개 고르기 

알파벳 조합 100개 중 4개 골라 CHRISTMAS 단어 만들기 

// 3번
// 경우의 수 == > 재귀
string str[100]; // 스티커 종류 개수
string path[4];
int used[100];
int sum = 0;
int n;
void recur(int level) {
	// level = 4 : 4개고름
	if (level == 4) {
		//cout << path[0]+ path[1] + path[2] + path[3]<< endl;
		if (path[0] + path[1] + path[2] + path[3] == "CHRISTMAS")	// *** path 문자열의 concat이 "CHRISTMAS"와 같다면, 갯수 세기
			sum++;
		return;
	}
	// branch = n : n개 중
	for (int i = 0; i < n; i++) {
		path[level] = str[i];		// *** 해당 level에 스티커 고르기
		used[i] = 1;
		recur(level + 1);
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str[i];		// 배열로 받기
	}
	recur(0);
	cout << sum;
	return 0;
}

 

 

부분합구하기 

// 7 번		// 이진 트리 BackTracking -부분합 구하기!!

int path[5] = { 0 };
int arr[5];
int cnt = 0;

void recur(int lv, int sum) {			// 부분 합을 항상 같이 전달
	// level = 최대 5자리
	if (lv == 5) {
		if (sum >= 10 && sum <= 20)
			cnt++;
		return;
	}
	// branch = O or X 두가지			// 정해진 수5 개를, 각각 사용할지, 안할지로 정함 
	for (int i = 0; i < 2; i++) {
		path[lv] = i*arr[lv];			// 안쓰거나, or 해당 수를 쓰거나 
		recur(lv + 1, sum + i*arr[lv]);
	}
}

int main() {
	for (int i = 0; i < 5; i++) {
		cin >> arr[i];
	}
	recur(0,0);
	cout << cnt;
	return 0;
}