안녕하세요! 재귀함수에 관해서 질문드립니다

교안 p.118에 있는 재귀함수 예제문제에서

for(int i = depth; i < n; i++){

swap(v[i], v[depth]); //첫번째 swap(v[i], v[depth]);

makePermutation(n, r, depth + 1);

swap(v[i], v[depth]); //두번째 swap(v[i], v[depth]);

} return;

이렇게 예제가 나와있습니다.

제가 이해한 바로는,

함수 makePermutation에 (3, 3, 0)을 대입하면

i와 depth는 0으로 첫번째 swap(v[i], v[depth]); 은 swap(0,0)이 되고

for문 안에 있는 makePermutation에 의해 매개변수 (3, 3, 0)이 (3, 3, 1)로 변하게되어

(3, 3, 1)에 해당하는 함수 makePermutation을 실행하게 되어 다시 첫번째 swap(v[i], v[depth]);이 실행되는 방식인 것으로 이해를 하였습니다.

여기서 첫번째 swap(v[i], v[depth]); 의 역할은 이해가 가지만 두번째 swap(v[i], v[depth]); 의 역할은 이해가 가지 않아서 질문 드렸습니다. 감사합니다!

안녕하세요 1209님 ㅎㅎ

해당 부분은 원복입니다.

예를 들어

1 2 3

에서

1 3 2로 바꿨다면

다시

1 2 3으로 바꾸는 코드입니다.

저 코드는 경우의수를 위해 존재하는 거에요.

좀 더 쉽게 생각을 해보면,

이렇게 그래프가 있다고 할 때 1, 2, 3과 1, 2,4를 뽑고 싶어요.

이 때 1, 2, 3을 뽑고 !!! 다시 2로 돌아와서 1, 2 상태에서 1, 2, 4를 뽑는 것이죠.

그러면 이 때 3을 뽑는 "상태"를 되돌려야 되요.

즉, {1, 2} 상태에서 {1, 2, 3}으로 갔다가 {1, 2}로 와서 {1, 2, 4}로 가야 하는 것이죠.

그런 것을 위한 "원복"코드입니다.

해당 부분은 디버깅을 하면서 이해하시면 이해가 되는데요.

제가 해당 코드에 디버깅 코드를 넣어봤는데요.

참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std;    
int a[3] = {1, 2, 3};
vector<int> v; 
void printV(vector<int> &v){
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << " ";
    }
    cout << "\n";
}
void makePermutation(int n, int r, int depth){
    if(r == depth){
        printV(v);
        return;
    }
    for(int i = depth; i < n; i++){ 
        swap(v[i], v[depth]);
        
        cout << i << " : " << depth << " 바꾼다!!\n";
        printV(v);
        
        makePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
        
        cout << i << " : " << depth << " 다시 바꾼다!!\n"; 
        printV(v);
        printV(v);
    }
    return; 
}
int main(){ 
    for(int i = 0; i < 3; i++)v.push_back(a[i]); 
    makePermutation(3, 3, 0); 
    return 0; 
} 
/*
0 : 0 바꾼다!!
1 2 3
1 : 1 바꾼다!!
1 2 3
2 : 2 바꾼다!!
1 2 3
1 2 3
2 : 2 다시 바꾼다!!
1 2 3
1 2 3
1 : 1 다시 바꾼다!!
1 2 3
1 2 3
2 : 1 바꾼다!!
1 3 2
2 : 2 바꾼다!!
1 3 2
1 3 2
2 : 2 다시 바꾼다!!
1 3 2
1 3 2
2 : 1 다시 바꾼다!!
1 2 3
1 2 3
0 : 0 다시 바꾼다!!
1 2 3
1 2 3
1 : 0 바꾼다!!
2 1 3
1 : 1 바꾼다!!
2 1 3
2 : 2 바꾼다!!
2 1 3
2 1 3
2 : 2 다시 바꾼다!!
2 1 3
2 1 3
1 : 1 다시 바꾼다!!
2 1 3
2 1 3
2 : 1 바꾼다!!
2 3 1
2 : 2 바꾼다!!
2 3 1
2 3 1
2 : 2 다시 바꾼다!!
2 3 1
2 3 1
2 : 1 다시 바꾼다!!
2 1 3
2 1 3
1 : 0 다시 바꾼다!!
1 2 3
1 2 3
2 : 0 바꾼다!!
3 2 1
1 : 1 바꾼다!!
3 2 1
2 : 2 바꾼다!!
3 2 1
3 2 1
2 : 2 다시 바꾼다!!
3 2 1
3 2 1
1 : 1 다시 바꾼다!!
3 2 1
3 2 1
2 : 1 바꾼다!!
3 1 2
2 : 2 바꾼다!!
3 1 2
3 1 2
2 : 2 다시 바꾼다!!
3 1 2
3 1 2
2 : 1 다시 바꾼다!!
3 2 1
3 2 1
2 : 0 다시 바꾼다!!
1 2 3
1 2 3
*/

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변