알고리즘 study -12-

재귀호출을 이용한 완전탐색(Advanced Brute-Force) / Backtracking

---

ex> N개의 카드가 있고, 각각 1부터 N까지 번호를 가진다.
이를 한 줄로 세울 수 있는 모든 경우를 출력해라.

// ex> N = 3
for(int i = 1; i <= 3; i++){
	for(int j = 1; j <= 3; j++){
    		for(int k = 1; k <= 3; k++){
        		...
        }
    }
}

---

N중 for문을 구현해야함

But, 위 방식으로는 N이 더 커진다면 구현하기 까다롭다

---

재귀호출을 통한 N중 for문 구현

int n = 3;
doRecursion(int x){  // x번째 for문을 실행
  if x>n -> print Nubers
  else{
     for(int i = 1; i<=n; i++){
      if 아직 숫자 i가 없었다면
      x 번째 for에 숫자 i를 등록하고
      doRecursion(x+1);
      }
   }
}

---

#include <stdio.h>

void getResult(int current, int n, int result[]);
bool isNotContaining(int result[], int i, int n);

void getResult(int current, int n, int result[]){
  if(current >= n){  // 이미 n개의 for문이 나왔다는 뜻
    for(int z = 0; z<n; z++){
      printf("%d ", result[z]);
    }
    printf("\n");
  }
  else{
    for(int i = 1; i<=n; i++){
      if(isNotContaining(result, i, n)){
        result[current] = i;
        getResult(current+1, n, result);
        result[current] = 0; //초기화 필요
      }
    }
  }
}

bool isNotContaining(int result[], int i, int n){
  bool inc = true;
  for(int j = 0; j<n; j++){
    if(result[j] == i){
      inc = false;
      break;
    }
  }
  return inc;
}

int main() {

  int n;
  int arr[5] = {0,};
  
  scanf("%d", &n);
  
  getResult(0, n, arr);

  return 0;
}

// getResult : result[]에 답을 채워 나가면서 출력하는 함수
// 현재 current 인덱스를 채울 차례이며, 총 n개의 숫자를 채워야 하는 상황

---

재귀호출을 사용하여 순열 구하기

// N개의 알파벳 중에서 R개를 나열하는 모든 경우의 수를 출력하시오

// -->> 다중 for문으로 해결할 시 for문 R개 필요

#include <stdio.h>

const int MAX = 105;

int n, r;
char result[MAX];
bool check[MAX];  // 알파벳 순서대로 result에 있는지 체크

void getResult(int x){
  // x 번째 for문을 돌려야 함
  
  if(x >= r){
    printf("%s\n", result);
  }
  else{
    for(int i = 0; i<n; i++){
      char alpha = i + 'a';
      if(check[i] == false){
        result[x] = alpha; 
        check[i] = true; // i는 이제 나왔으므로 true
        
        getResult(x+1);
        // getResult(x+1)에서
        // x번째에 i를 넣는 모든 경우를 이미 다 고려함
        
        check[i] = false; // 초기화 필요
        // result에서 뺄 것이므로 false로 다시 초기화 필요
        
      }
    }
  }
}

int main() {
  
  scanf("%d %d", &n, &r);
  
  getResult(0);

  return 0;
}

---