재귀함수

void Quest(int Level)
{
    if(Level >= 2)
    {
      return;
    }
    
    Quest(Level + 1);
    Quest(Level + 1);
}

int main()
{
    Quest(0);
    
    return 0;
}

위와 같은 코드를 생각해보자.

Quest 함수는 재귀함수로 본인 내에서 Level을 1 증가한 Quest 함수를 재호출하는 형태로 되어 있다.

 

이게 만약 실행된다면 아래와 같은 순서로 실행이 될 것이다. 

 

 

코드는 한 줄씩 실행된다는 것을 이해하면 알기 쉽다.

 

1. 우선 Quest(0)이 실행된다.

2. Quest(0)에서 Quest(0 + 1);이 호출된다. 여기서 중요한 것은 두개의 Quest(Level + 1) 중 위에 있는 함수가 호출된다는 것이다.

3. Quest(1)에서는 다시 Quest(1 + 1)이 호출된다.

4. 이제 Level이 2에 도달하였으므로 Return하게 된다.

5. 이때 Return하게 되면 어디에 위치하는가? 바로 Quest(1) 함수내에서 Quest(1 + 1)의 2개 중 첫번째 함수가 종료된 것이다. 그러므로 두번째  Quest(1 + 1)이 다시 호출되게 된다.

 

이로 인해 자녀 먼저 탐색을 시도하게 되는데 이처럼 아래로 내려가는 것을 그래프에서는 깊이라고 하고, 옆으로 넘어가는 것을 너비라고 한다.

 

이는 깊이 우선 탐색(Depth First Search, DFS)이 되는 것이다.

 

void Quest(int Level)
{
    if(Level >= 2)
    {
      return;
    }
    
    for(size_t i = 0; i < 2; ++i)
    {
        Quest(Level + 1);
    }
    
}

 

반복문을 통해 코드를 좀 더 간결하게 만들어줄 수 있다.

 

탐색 경로 기록

 

우리가 재귀함수를 통해 탐색을 하다보면 정확한 위치를 알기 어려운 경우아 많이 발생한다.

이를 해결하기 위해 각 함수를 들어갈때마다 몇번째 Level(Index)의 어느 자식인지(Value) 별도의 배열을 만들어서 저장을 하는 방식으로 탐색 경로를 기록해 놓기도 한다.

 

char path[10] = "";

void Quest(int Level)
{
    if(Level >= 3)
    return;
    
    for(size_t i = 0; i < 2; ++i)
    {
      path[Level] = 'A' + i;
      Quest(Level + 1)
      path[Level] = 0;
    }
}

 

실제로 해당 코드의 Path를 출력해보면 AAA, AAB, ABA와 같이 출력되는데 이는 순열과 조합 문제의 해결 방법이기도 하다.

 

중복이 가능한 경우와 가능하지 않는 경우, 뽑을 수 있는 카드가 더 많은 경우(for문의 반복 횟수 증가)등 상황에 맞게 사용할 수 있다.

 

또한 Path의 값을 사람이라면 사람의 성만 따서 "KPJ"를 넣는 식으로 사람들의 순서를 짜는 방식도 가능하다.

 

재귀함수 가지치기

1. 특정 Path 자체에 들어가지 않기

char path[10] = "";

void Quest(int Level)
{
    if(Level >= 3)
    return;
    
    for(size_t i = 0; i < 2; ++i)
    {
      if('A' + i == 'A' && Level == 0)
      continue;
      
      path[Level] = 'A' + i;
      Quest(Level + 1)
      path[Level] = 0;
    }
}

 

위와 같이 if문을 추가하여 최초에 A 가지쪽으로 들어가지 않도록 하면 A로 시작되는 Path는 출력되지 않는다.

중요한것은 중복 제거가 아니라 특정 가지로 진입하지 않도록 하는 코드이다.

 

2. 연속된 중복을 제거

BBA, AAC, CCB, ABB 처럼 연속해서 나오는 경우만 제거

char path[10] = "";

void Quest(int Level)
{
    if(Level >= 2 && path[Level - 2] == path[Level -1])
    return;
    
    if(Level >= 3)
    {
      std::cout << path << std::endl;
      return;
    }
    
    
    for(size_t i = 0; i < 2; ++i)
    {
      if('A' + i == 'A' && Level == 0)
      continue;
      
      path[Level] = 'A' + i;
      Quest(Level + 1)
      path[Level] = 0;
    }
}

 

3.  Path내 중복제거

ABA, BCB 와 같이 동일한 Path가 나오지 않도록 함.

char path[10] = "";
int UsedPath[3] = {};

void Quest(int Level)
{
    if(Level >= 2 && path[Level - 2] == path[Level -1])
    return;
    
    if(Level >= 3)
    {
      std::cout << path << std::endl;
      return;
    }
    
    
    for(size_t i = 0; i < 2; ++i)
    {
      if(UsedPath[i] == 1)
      continue;
      
      if('A' + i == 'A' && Level == 0)
      continue;
      
      UsedPath[i] = 1;
      path[Level] = 'A' + i;
      Quest(Level + 1)
      path[Level] = 0;
      UsedPath[i] = 0;
    }
}

 

해당 Path를 이미 사용했는지 안했는지 기록할 배열을 추가하여 함수를 호출할 때마다 해당 Path의 Index에 사용했다는 의미로 1을 기록하도록 한다.

 

이를 이용해 해당 함수 호출전 UsedPath 배열에서 값을 확인하고 1인 경우 들어가지 않도록 한다.

 

3차원 배열

2차원 배열이 여러개 있는 형태

3차원 배열이라고하여 우리가 생각하는 그 3차원 도형 형태의 배열이 아니다.

 

 

int arr[3][3][3] = {};

for(size_t i = 0; i < 3; ++i)
{
    for(size_t j = 0; j < 3; ++j)
    {
        for(size_t k = 0; k < 3; ++k)
        {
           arr[i][j][k] = 1;
        }
    }
}

 

그러나 가독성이 떨어지므로 일반적으로 잘 사용하지 않으며, []를 추가함으로써 4차원, 5차원도 가능하다.