Level 23 : 재귀호출 4 : used + 가지치기

백트래킹 하다가 헷갈려서 가지치기 복습하기

가지치기란?

1)리턴조건을 추가하는것
2)진입하고싶지 않은 구간이 있을때, 인위적으로 막는것

가지치기 방법

1)진입후 바로나가기

2)아예 진입 안하기

중요1.4장중 3장만 뽑기

중요2.via배열을 이용하여 중복선택 막기

Q. path에서 값을 넣을때 왜 path[lev] 이지?
첨에 값을 입력할때 시작점이 무엇을 선택하는지 모르기 때문
dfs에서는 시작점을 알려주는데, 백트래킹은 모든 경우의수를 다보기때문에 path[0] 의 값은 모른다.

#include <iostream>
#include <string>
using namespace std;


string names = "BOTK";

char path[10];
int cnt = 0;
void run(int lev) {
	if (path[lev - 2] == 'B' && path[lev - 1] == 'T')return;
	if (path[lev - 2] == 'T' && path[lev - 1] == 'B')return;
	if (lev == 4) {
		cnt++;
		return;
	}
	//아직 시작점이 정해져 있지 않으니깐.
	for (int i = 0; i < 4; i++) {
		path[lev]=
			//근데 왜 lev+1이 아니고 lev이지?,,
	}
}
int main() {
	run(0);

	return 0;
}

해결!!