[3] 백트래킹 공부

Q. 주사위 게임을 했을 때, 나올 수 있는 모든 경우의 수를 구해보자.

- 입력 : 주사위의 개수 → 정수 1개

- 출력 : 해당 주사위로 나올 수 있는 주사위 눈의 모든 경우

 

주사위 N개가 있다면, N개의 주사위에서 각 주사위 눈을 선택

ex. N = 3이면, 1번 주사위 -> 2번 주사위 -> 3번 주사위 순으로 작동

즉, 현재(now)에 a를 넣으면 다음(next)에서는 a+1을 넣음.

1부터 6 중에서 하나를 뽑고 다음 주사위로 넘어감.

int path[10];

void func(int a){
	//지금 a번째 주사위를 뽑을 차례
	
	// 0~N-1번 : 정상
	// N번 주사위~ : 존재하지 않는 주사위
    // N번의 주사위까지 도달 -> 0~N-1번 주사위에서 모두 눈을 선택 완료.
	if(a>=N){
    	for(int i=0; i<N; i++)
        	cout << path[i] << " ";
        cout << "\n";
		return;
	}
	// i : 1~6 주사위 눈 
	for(int i=1;i<=6;i++){
    	// 기록
        // a번째 차례에서 i 눈을 뽑음.
        path[a] = i;
        
		// a+1번째 주사위를 뽑으러 가자
		func(a+1);
	}
} // main 함수에서 func(0)으로 동작.

 

모든 조합 경우들을 기록하고 싶어 → path 사용   ex. int path[10];

- index : 박스 번째

- value : 해당 박스에서 뽑은 주사위 눈

 

DAT

- index : 층(level)

- value : 이 층에서 어떤 경우를 선택했는지

1) 기저조건 : 문제에서 주어지는 횟수

2) 재귀구성 : 문제에서 주어지는 각 횟수의 경우의 수

void func(int level){
	//기저 조건
	if(level == N) return;
}

int main(){
	//진입할 때
	// -> path 기록 : 내가 지금 level에서 어떤 선택을 할지
	path[level] = i;
	DAT[i] = 1;

	fuc(level + 1); // 다음 진입

      // 빠져 나올 때
      // -> 위에서 기록 해제 (초기화)
	path[level] = 0;
	DAT[i] = 0;
}

백트래킹 : 일단 가는데 아니라면 돌아가기

가지치기 : 아니라면 가지 않기

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

char path[10]; 
char dir[] = { 'L', 'R' };

void func(int level){
	// backtracking ( 한 번 먼저 가보고, 잘못된 길이면 돌아간다)
    if (level > 2 && path[level - 1] == 'L' && path[level - 2] == 'L')
        return;
        
	// 기저 조건
    if (level == 3) {    
        for (int i = 0; i < level; i++)
            cout << path[i] << " ";
        cout << '\n'; 
        return; 
    }

    // 재귀 구성
    for (int i = 0; i < 2; i++) {
        // 가지치기 (내가 가려는 길을 미리 판단하고 안간다)
        /* 
        if (level > 0 && dir[i] == 'L' && path[level - 1] == 'L')
            continue; 
        */ 
        path[level] = dir[i];
        func(level + 1); 
        path[level] = 0;
    }
}

int main(){
	func(0); 
}