C++ 순열 구현

코딩테스트에 자주 나오는 개념인 순열을 파헤쳐보았다. 나는 dfs를 이용하여 순열을 구현했다.

• 알고리즘 목표
  주어진 배열의 원소들의 조합을 모두 구하고, 총 개수를 출력해라.
• 입력
  int array 와 r 값 (단 r<=array의 길이)
• 출력
  nPr의 모든 경우의 수를 출력하고, 순열의 총 개수 또한 출력

나는 이해하기 쉽게 하기 위하여 array와 r을 다음과 같은 값으로 고정하였다.
array = [1,2,3,4,5] | r = 2 따라서 5P2모든 조합인
(1,2),(1,3),(1,4),(1,5)….(5,1),(5,2),(5,3),(5,4)와 조합의 개수인 20을 출력하면 된다. 코드를 먼저 보자.

#include<iostream>
#include<vector>
using namespace std;
vector<int> v = {1,2,3,4,5};
vector<bool>visited(5,false);
int cnt=0;
void dfs(vector<int> &out,vector<bool>&visited,int r,int idx){
    if(r==0){ //base case
        cout<<"(";
        for(int i=0;i<out.size();i++){
            if(i==out.size()-1)
                cout<<out[i]<<")";
            else cout<<out[i]<<",";
        }
        cout<<"\n";
        cnt++;
        return;
    }
    for(int i=0;i<v.size();i++){
        if(!visited[i]){
            visited[i] = true;
            out.push_back(v[i]);
            dfs(out,visited,r-1,idx+1);
            out.pop_back();
            visited[i] = false;
        }
    }
}

int main(){
    vector<int> out;
    dfs(out,visited,2,0);
    cout<<"Total : "<<cnt<<"\n";
    return 0;
}

그리고 바로 흐름을 그림으로 그려보았다. 왼쪽 상단에서 부터 화살표를 따라가면 이해가 될 것 같다.
수평선은 같은 level에 있는 함수들을 표현하기 위해 그어봤다. dfs(out,visited,2)로 맨 처음으로 함수를 호출하면 함수 내부에 있는 반복문을 통해 다음 재귀 함수를 호출한다. base case를 만나 리턴이 되면 다시 상위 함수로 돌아가 out.pop_back()과 visited[i] = false를 진행하고 다음 반복문으로 넘어간다. 이 과정을 계속 반복한다.

그리고 첫번째 재귀함수에서 리턴이 되어 inital call로 프로그램의 흐름이 넘어오면, 똑같이 out.pop_back()을 하고 visited[i] = false를 진행한다. 내가 진행한 예시의 경우에는 out empty일 것이다. 그리고 다음 반복문으로 넘어가 또 재귀호출을 하면 된다.

(1,2)
(1,3)
(1,4)
(1,5)
(2,1)
(2,3)
(2,4)
(2,5)
(3,1)
(3,2)
(3,4)
(3,5)
(4,1)
(4,2)
(4,3)
(4,5)
(5,1)
(5,2)
(5,3)
(5,4)
Total : 20

성공적이다.