알고리즘 - 백트래킹

백트래킹

: 해를 찾는 도중 막힌 경우(답이 없거나, 말단노드 인 경우) 되돌아가서 다시 해를 찾는 기법
👉 지금 경로가 정답일 가능성이 없다면 해당 경로를 가지 않고 되돌아 감(가지치기)
- 가지치기를 통해 연산양이 줄어든다.

• 특징

• Backtrack(역추적)하는 알고리즘, 탐색 이전 단계로 되돌아갈수 있어야 함(재귀)
• 일반적으로 재귀를 이용한 DFS 구현

백트래킹 구현 방법 (경로 이용)

필요 - 값 저장 배열, 방문 체크 배열

순열 방식

1. 분기 - 각 노드를 방문 해서 경로가 유효하다면 방문 체크, 경로가 정답이 아니라면 방문 체크 해제
2. 종료 - 해당 노드를 모두 체크한 경우 종료

ex) A,B,C -> 2개 선택
참고 코드

//종료
static void permutation(int r){
	if(r == R) // R : r개 전부 뽑은 경우)
    	return
}

//분기
for(int i =0; i<arr.length; i++){
	if(isVisited[] == true) continue;
    select[r] = i;
    isVisited[i] = true;
    permutation(r+1);
    isVisited[i] = false;	//중복허용X 마킹해제 (방문한 노드 재방문X)
}

조합 방식

static void combination(int start, int r){
	if(r >= R){
    	for(int i=0; i<R; i++){
        	System.out.print(arr[select[i]]);
        }
        cnt++;
        System.out.println();
        return;    
    }
    for(int i=start; i<arr.length; i++){
    	select[r] = i;
        combination(i+1, r+1);
    }
}