DFS를 이용한 순열 만들기

 

얍문님의 글을 보고 공부했습니다.

https://yabmoons.tistory.com/100

[ 순열과 조합 구현 ] - 재귀를 통한 구현(2 - 순열) (C++)

 

순열과 조합

순열은 순서가 상관이 있는 수의 집합이다.

순열에서는 {1,2,3}과 {2,1,3}이 다르다.

 

조합은 순서가 상관이 없는 수의 집합이다.

조합에서는 {1,2,3}과 {2,1,3}이 같다.

 

 

{1,2,3,4,5}라는 수의 집합을 3개를 뽑아서 순열로 다음과같이 만들자.

1,2,3

1,2,4

1,2,5

2,1,3

2,1,4 ...

 

 

재귀로 구현된 DFS를 이용해서 만들수 있다.

DFS는 백트래킹의 방법중 하나이다.

 

#include <iostream>
#include <vector>

#define MAX 6
using namespace std;

int arr[MAX];
bool mark[MAX];
vector<int> v;

void Print() {
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ' ';
    }
    cout << '\n';
}

void DFS(int depth) {
    // 3개 출력, depth가 4에 도달하면 출력후 이전 depth로 돌아감
    if(depth == 4) {
        Print();
        return;
    }

    for(int i = 1; i < MAX; i++) {
    	// 백트래킹 
        // 이미 방문했다면 continue
        if(mark[i]) continue;
        // 방문 체크
        mark[i] = true;
        // 해당 숫자 벡터에 삽입
        v.push_back(arr[i]);

        // 다음 depth로 이동
        DFS(depth+1);

        // 이 아래 부터는 Print()로 출력한 이후임.
        // 출력 했으니 마지막 숫자를 pop 하고 방문여부를 false로 되돌림
        v.pop_back();
        mark[i] = false;
    }
}


int main() {
	// 1, 2, 3, 4, 5
    for(int i = 1; i < MAX; i++) {
        arr[i] = i;
    }

    DFS(1);
}

 

먼저 DFS 함수에 1을 전달하면서 재귀가 시작된다.

 

DFS(1)

for문의 i=1부터 시작.

1번을 방문했으므로 mark[1]을 체크한다.

1에 해당하는 arr[1]을 벡터 v에 삽입한다.

현재 v = {1}

현재 mark[] = T F F F F

다음 depth인 DFS(2)로 이동한다 

 

DFS(2)

for문의 i=1부터 시작하는데 mark[1] = true이므로 continue.

 

i=2

2번을 방문했으므로 mark[2]를 체크한다.

2에 해당하는 arr[2]를 벡터 v에 삽입한다.

현재 v = {1,2}

현재 mark[] = T T F F F

다음 depth인 DFS(3)으로 이동한다.

 

DFS(3)

i=1, mark[1] = true이므로 continue.

i=2, mark[2] = true이므로 continue.

 

i=3

3번을 방문했으므로 mark[3]을 체크한다.

3에 해당하는 arr[3]를 벡터 v에 삽입한다.

현재 v = {1,2,3}

현재 mark[] = T T T F F

다음 depth인 DFS(4)로 이동한다.

 

DFS(4)

depth == 4 이므로 if문에 의해서 현재까지의 벡터 v를 출력하고 이전 depth로 이동한다.

출력 = {1,2,3}

 

DFS(3)

재귀함수 DFS(depth+1)아래 (여기서 depth==3) 코드 부터 실행된다.

즉 v = {1,2,3}에서 마지막 요소인 3을 pop하고 

방문여부 mark도 false로 되돌린다.

현재 v = {1,2}

현재 mark[] = T T F F F

 

재귀하기 전에 depth 3에서 i=3까지 실행했으므로 

i=4

4번을 방문했으므로 mark[4] 체크.

4에 해당하는 arr[4]를 벡터 v에 삽입.

현재 v = {1,2,4}

현재 mark[] = {T T F T F}

다음 depth인 DFS(4)로 이동한다.

 

DFS(4)

depth == 4이므로 현재 벡터 v를 출력하고 이전 depth로 이동.

출력 = {1,2,4}

 

DFS(3)

재귀함수 DFS(depth+1)아래 (여기서 depth==3) 코드 부터 실행된다.

즉 v = {1,2,4}에서 마지막 요소인 4을 pop하고 

방문여부 mark도 false로 되돌린다.

현재 v = {1,2}

현재 mark[] = T T F F F

 

재귀하기 전에 depth 3에서 i=4까지 실행했으므로 

i=5

5번을 방문했으므로 mark[5] 체크.

5에 해당하는 arr[5]를 벡터 v에 삽입.

현재 v = {1,2,5}

현재 mark[] = {T T F F T}

다음 depth인 DFS(4)로 이동.

 

DFS(4)

depth==4이므로 현재 벡터 v를 출력하고 이전 depth로 이동.

출력 = {1,2,5}

 

DFS(3)

재귀함수 DFS(depth+1)아래 (여기서 depth==3) 코드 부터 실행된다.

즉 v = {1,2,5}에서 마지막 요소인 5을 pop하고 

방문여부 mark도 false로 되돌린다.

현재 v = {1,2}

현재 mark[] = T T F F F

 

이제 for문의 1부터 5까지 모두 수행했으므로 depth 3에서의 for문은 끝났다.

함수가 종료되고 이전 depth로 다시 돌아간다.

 

DFS(2)

재귀함수 DFS(depth+1)아래 (여기서 depth==2) 코드 부터 실행된다.

즉 v = {1,2,}에서 마지막 요소인 2을 pop하고 

방문여부 mark도 false로 되돌린다.

현재 v = {1,}

현재 mark[] = T F F F F

 

이전 재귀에서 i=2까지 수행했으므로

i=3

3번을 방문했으므로 mark[3] 체크.

3에 해당하는 arr[3]를 벡터 v에 삽입.

현재 v = {1,3}

현재 mark[] = {T F T F F}

다음 depth인 DFS(3)로 이동.

 

DFS(3)

i=1부터 시작한다.

그런데 mark[1]은 이미 방문했으므로 continue.

 

i=2

2번을 방문했으므로 mark[2] 체크

2에 해당하는 arr[2]를 벡터 v에 삽입 

현재 v = {1,3,2}

현재 mark[] = {T T T F F}

다음 depth인 DFS(4)로 이동.

 

DFS(4)

depth==4이므로 현재 벡터 v를 출력하고 이전 depth로 이동.

출력 = {1,3,2}

 

...

 

 

이런식으로 수의 집합에서 내가 원하는 만큼의 갯수의 숫자를 뽑아 순열을 만들수 있다.

재귀는 아직까지도 햇갈린다.

재귀를 풀때는 버려지는 세세한 부분까지는 생각하지 않고 푸는게 상책인것 같다.