[YYBASIC0208/얌얌코딩] 재귀 함수 탐색 경로 기록하기

 

 

깊이 우선 탐색 (Depth-First Search; DFS)

• 깊이 우선 탐색(DFS)은 가능한 한 깊게 탐색한 후에 더 이상 갈 수 없을 때 돌아오는 방법입니다.

너비 우선 탐색 (Breadth-First Search; BFS)

• 너비 우선 탐색(BFS)은 한 층에서 모두 탐색한 다음 다음 층으로 넘어가는 방법입니다.

경로 기록을 진행하는 이유

• 경로 기록은 탐색 중에 지나온 길을 메모하거나 저장하는 것입니다.
• 탐색했던 경로를 기록하면 나중에 돌아갈 길이나 잘못 간 길을 쉽게 찾을 수 있습니다.

 

// YYBASIC02_08
#include <iostream>
using namespace std;

char path[10] = "";
char name[10] = "JHY";

void run1(int level)
{
    if (level == 3)
    {
        cout << "path : " << path << endl;
        return;
    }

    path[level] = 'A';  // 왼쪽으로 들어갈 예정이다
    run1(level + 1);     // 왼쪽으로 들어갔다
    path[level] = 0;    // 빠져나왔다

    path[level] = 'B';  // 오른쪽으로 들어갈 예정이다
    run1(level + 1);     // 오른쪽으로 들어갔다
    path[level] = 0;    // 빠져나왔다
}

void run2(int level)
{
    if (level == 3)
    {
        cout << "path : " << path << endl;
        return;
    }

    for (size_t i = 0; i < 2; i++)
    {
        path[level] = 'A' + i;  // 'A'는 아스키 코드이므로 i를 더하여 B를 표현할 수 있다
        run2(level + 1);
        path[level] = 0;
    }
}

void run3(int level)
{
    if (level == 4)
    {
        cout << "path : " << path << endl;
        return;
    }

    for (size_t i = 0; i < 3; i++)
    {
        path[level] = name[i];
        run3(level + 1);
        path[level] = 0;
    }
}

void main()
{
    cout << "< run1(int level) >" << "\n";
    run1(0);
    memset(path, '\0', sizeof(path));       // path를 공백으로 초기화
    // cout << "initialize path : " << path << endl;

    cout << "\n< run2(int level) >" << "\n";
    run2(0);
    memset(path, '\0', sizeof(path));
    // cout << "initialize path : " << path << endl;

    // 청소 당번
    cout << "\n< run3(int level) >" << "\n";
    run3(0);
}

 

재귀 함수 경로 기록

• `run1()` 과 `run2()` 는 재귀 함수의 탐색 과정의 경로를 기록하는 함수로, `run2()` 의 경우 for loop를 이용하여 코드 중복을 줄였습니다.
• 탐색 경로를 기록하는 방법은 다음과 같습니다.
  1. 탐색 경로를 기록하기 위해 path라는 이름의 배열을 생성합니다.
  2. 왼쪽으로 이동할 경우 ‘A’, 오른쪽으로 이동할 경우 ‘B’를 path에 저장합니다.
  3. 재귀에서 빠져나올 때는 path를 0으로 초기화하여 남아 있는 경로를 명확하게 합니다.

경우의 수

• 순열은 요소들을 중복 없이 특정한 순서로 나열하는 일입니다.
• 조합은 특정한 집합에서 중복 없이 일부를 선택하는 다양한 방법입니다.
• 경우의 수 알고리즘 문제는 대부분 재귀 함수를 이용하여 해결할 수 있으며, 이를 통해 더욱 효율적으로 문제를 풀 수 있습니다.

LV07 재귀함수 탐색경로 기록하기