[C++] 백트래킹 정답 찾으면 다른 경우 안보기

단일 해 탐색 가지치기

백트래킹에서 정답을 찾았으면 다음 경우를 볼 필요 없이 탐색을 종료하고 싶을 때가 있다.

아래와 같이 성공하면 true를 반환하여 for문의 다음 idx를 하지 않으면 된다. 

bool dfs(int depth) {
	// 정답 찾음
    if(depth == n)
        return true;

    for(int i = 0; i < arr.size(); i++) {
        if(!check()) continue;
		
        // 정답을 찾았으니, 이후 경우를 볼 필요가 없음
        if(dfs(depth + 1)) return true;
    }
    
    return false;
}

 

※ exit(0)를 하는 방법도 있지만 선호하지 않음