[개념] 조합, 순열 + DFS,BFS

[순열, 조합]

순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다.

말 그대로, 순서가 존재하는 열 이라는 것이다.

즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 등.. 모두 다른 결과를 가져온다. 순서가 다르기 때문이다.

 

조합은 순서가 상관이 없는 모임을 의미한다. 순서가 상관 없기 때문에

 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은것으로 취급을 한다. 순서가 상관없기 때문에

1, 2, 3 이라는 3개의 숫자로 이루어져있다는 점에서 똑같은 취급을 하는 것이 조합이다.

 

 

 

1. 조합이용 - 5개중 3개 뽑아보기

#include<iostream>
 
#define MAX 5
using namespace std;
 
int Arr[MAX];
bool Select[MAX];
 
void Print()
{
    for (int i = 0; i < MAX; i++)
    {
        if (Select[i] == true)
        {
            cout << Arr[i] << " ";
        }
    }
    cout << endl;
 
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == 3)
    {
        Print();
        return;
    }
 
    for (int i = Idx; i < MAX; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;

        DFS(i, Cnt + 1);
        Select[i] = false;
    }
}
 
int main(void)
{
    Arr[0] = 1;
    Arr[1] = 2;
    Arr[2] = 3;
    Arr[3] = 4;
    Arr[4] = 5;
 
    DFS(0, 0);
}

 

 

여기서 DFS(Idx, Cnt) 가 실행되는 순서만 살펴보자

* 앞으로 이렇게 표 형식으로 된건 전부 DFS(Idx,Cnt)가 실행될 때를 나타냄을 의미

Idx	Cnt
0	0
0	1
1	2
2	3

 

DFS(2,3) 여기가 실행될 때, 다음 조건에 만족하여 Print()가 실행된다

   if (Cnt == 3)
    {
        Print();
        return;
    }

 

Select[i] == true 인 인덱스는 0,1,2 이다

void Print()
{
    for (int i = 0; i < MAX; i++)
    {
        if (Select[i] == true)
        {
            cout << Arr[i] << " ";
        }
    }
    cout << endl;
 
}

 

결과로 1,2,3이 출력 된다. 

그 후, return되어 돌아갈 위치를 생각해보자.

 

 

★ 재귀 후 도착한 위치 찾기

Idx=1,Cnt=2 로 돌아가보자

1번째 값이 선택되었으므로 지나가고

2번째 값이 선택되지 않았으므로, 선택한 후 

재귀를 호출했었다.  -> DFS(2,3) 시행 -------★ 도착

Select[2] = false 로 바꿔준다. (현재 Idx=2, Cnt=2인 상황)

        DFS(i, Cnt + 1);
        Select[i] = false;

 

반복문에 의해 i값이 ++ 되어 i=3이 된다. (현재 Idx=3, Cnt=2인 상황)

3번째 값이 선택되지 않았으므로 3번을 선택하고 DFS(3,3) 실행

Idx	Cnt
3	3

-> 현재 Select[0], Select[1], Select[3] 이 true 인 상태이다.

 

 

또다시 if문에 만족하여 출력이 진행된다

   if (Cnt == 3)
    {
        Print();
        return;
    }

결과로 1,2,4가 출력된다.

 

 

★ 재귀 후 도착한 위치 찾기

Idx=3, Cnt=2 일때로 다시 돌아가보자. (위에 똑같이 초록색으로 하이라이트 되어 있는 부분으로 돌아갔다고 생각하자)

3번째 값이 선택되지 않았으므로 3번을 선택하고 DFS(3,3) 실행 -------★ 도착

Idx=3, Cnt = 2인 상태므로 Select[3] = false 로 바꿔준다

반복문에 의해 i++ 되어 i = 4 가 된다. (현재 Idx=4, Cnt=2인 상황)

Select[4] = true로 바꿔주고 DFS(4,3) 가 실행된다

 

Idx	Cnt
4	3

-> 현재 Select[0], Select[1], Select[4] 이 true 인 상태이다.

 

또다시 if문에 만족하여 출력이 진행된다

   if (Cnt == 3)
    {
        Print();
        return;
    }

결과로 1,2,5가 출력된다.

 

 

★ 재귀 후 도착한 위치 찾기

Idx=4, Cnt=2로 돌아가보자.( 위에 똑같이 노란색으로 하이라이트 되어 있는 부분으로 돌아갔다고 생각하자)

Select[4] = true로 바꿔주고 DFS(4,3) 가 실행된다 -------★ 도착

Select[4] = false 로 바꿔준다

i++ 되어 i=5가 되려했지만 i<MAX여야 하므로, 반복문에 빠져나와 return되어 

이전의 재귀함수 호출 위치로 돌아간다. => 어디로 돌아가야할지 모를때는 재귀함수인 DFS(Idx, Cnt) 가 거론됐던 곳을 천천히 거슬러 올라가보자.

 

 

★ 재귀 후 도착한 위치 찾기

Idx=1,Cnt=1 로 돌아가보자. (* 한단계 이전의 DFS 재귀 위치로 돌아가는게 아닌 전전전...단계로 돌아갈 때 이 분홍색으로 표시하겠다)

1번째 값은 선택되지 않았으므로 Select[1]=true로 바꿔주고

DFS(1,2)를 실행한다 -------★ 도착

Select[1] = false로 바꿔준다.

반복문에 의해 i++이 되어 Idx=2, Cnt=1이 된 상태이다.

2번째 값은 선택되지 않았으므로 Select[2]=true로 바꿔주고

DFS(2,2)를 실행한다  

Idx	Cnt
2	2

-> 현재 Select[0], Select[2] 가 true 인 상태이다.

 

Idx=2, Cnt=2인 상태에서

2번째 값은 선택되었으므로 지나가고

i++된 후 Idx=3, Cnt=2인 상태이다.

3번째 값은 선택되지 않았으므로 Select[3]=true 로 바꿔주고

DFS(3,3)을 실행한다

Idx	Cnt
3	3

-> 현재 Select[0], Select[2], Select[3] 이 true 인 상태이다.

-> Cnt = 3이므로 Print()가 실행되어 1,3,4가 출력된다.

 

 

★ 재귀 후 도착한 위치 찾기

Idx=3, Cnt=2로 돌아가보자

2번째 값은 선택되었으므로 지나가고

3번째 값은 선택되지 않았으므로 Select[3]=true 로 바꿔주고

DFS(3,3)을 실행한다 -------★ 도착

Select[3] = false로 바꿔준다.

i++이 되어 Idx=4, Cnt=2 가 되었다.

4번째 값은 선택되지 않았으므로 Select[4]=true 로 바꿔준다.

DFS(4,3)이 실행된다.

Idx	Cnt
4	3

-> 현재 Select[0], Select[2], Select[4] 이 true 인 상태이다.

-> Cnt = 3이므로 Print()가 실행되어 1,3,5가 출력된다.

 

 

★ 재귀 후 도착한 위치 찾기

Idx=4, Cnt=2로 돌아가보자.

DFS(4,3)이 실행된다.  -------★ 도착

Select[4] = false로 바꿔준다.

i++이 되어 Idx=5가 되려 했지만 i<MAX 여야 하므로 반복문이 끝나 return되어

이전의 재귀 호출 위치로 돌아간다.

 

 

★ 재귀 후 도착한 위치 찾기

Idx=2, Cnt=1 으로 돌아가보자

2번째 값은 선택되지 않았으므로 Select[2]=true로 바꿔주고

DFS(2,2)를 실행한다  -------★ 도착

Select[2] = false로 바꿔준다.

i++이 되어 Idx=3, Cnt=1이 된 상태이다.

3번째 값이 선택되지 않은 상태이므로, Select[3]= true로 바꿔주고 DFS(3,2)를 실행한다. 

Idx	Cnt
3	2

-> 현재 Select[0], Select[3]가 true인 상태이다.

 

i++ 되고 4번째 값이 선택되지 않은 상태이므로, (현재 Idx=4, Cnt=2)

Select[4]= true로 바꿔주고 DFS(4,3)를 실행한다. 

Idx	Cnt
4	3

-> 현재 Select[0], Select[3], Select[4] 가 true인 상태이다.

-> 1,4,5가 출력된다.

return되어 이전의 재귀 호출 위치로 돌아간다.

 

 

★ 재귀 후 도착한 위치 찾기

Idx=4, Cnt=2 로 돌아가보자

Select[4]= true로 바꿔주고 DFS(4,3)를 실행한다. -------★ 도착

 

Select[4]=false로 바꿔주고 i++이 되어 Idx=5 가 되려 했지만 i<MAX 이므로

반복문에서 빠져나온다.

이전의 재귀위치를 찾아간다. 

 

(이하 생략!)

 

 

---

 

 

2. 순열이용 - 5개중 3개 뽑아보기

순열과 조합의 차이점은 순서가 있냐 없냐의 차이이다.

조합에는 순서가 없기 때문에, 과거에 시작점으로 삼았던 친구는 다시는 쳐다도 보지 말라는 식으로 설명을 했었다.

하지만, 순열은?? 과거에 시작점으로 삼았던 친구를 다시 한번 쳐다봐줘야 한다.

조합 → { 1, 2, 3 } = { 2, 1, 3 } 이므로, 시작점이 2가 되는 순간 더 작은 요소인 1은 쳐다도 보지 말아라 !

순열 → { 1, 2, 3 } != { 2, 1, 3 } 이므로, 시작점이 2가 되더라도 더 작은 요소인 1을 쳐다봐야 한다 !

라는 차이가 있다.

 

#include<iostream>
#include<vector>
 
#define MAX 5
using namespace std;
 
int Arr[MAX];
bool Select[MAX];
vector<int> V;
 
void Print()
{
    for (int i = 0; i < V.size(); i++)
    {
        cout << V[i] << " ";
    }
    cout << endl;
}
 
void DFS(int Cnt)
{
    if (Cnt == 3)
    {
        Print();
        return;
    }
 
    for (int i = 0; i < MAX; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Arr[i]);
        DFS(Cnt + 1);
        V.pop_back();
        Select[i] = false;
    }
}
 
int main(void)
{
    Arr[0] = 1;
    Arr[1] = 2;
    Arr[2] = 3;
    Arr[3] = 4;
    Arr[4] = 5;
 
    DFS(0);
}

 

위의 코드를 보면 조합과의 차이부터 한번 봐보자. 일단 DFS를 호출하는 매개변수의 갯수부터 다르다.

시작점을 결정해 주는 친구인 Idx 변수가 없어졌고, Cnt 혼자서만 매개변수로 사용되어지고 있다.

Idx가 없어진 이유는 위의 설명만으로도 충분히 알 수 있을 것이다. 시작점을 다시 한번 쳐다봐야 하기 때문이다 !

또 큰 차이점으로는 Vector가 하나 쓰이고 있다. 물론 이부분은 본인의 코딩스타일 , 코딩방식 이기 때문에 참고만 하자 !

조합에서는 Vector를 사용하지 않은 이유가, 0 ~ Max까지 반복하면서 Select[i] = true인, 즉, 선택당한 놈들이 나올 때 마다 출력을 해주면 그만이었지만, 순열은 그게 안되기 때문이다.

순열도 조합처럼 출력을 한다고 생각해보자. { 1, 2, 3}을 선택해서 출력을 할 것이고, {2, 1, 3}이 되는 순간

{1,2,3}과는 다른 놈이기 때문에 {2,1,3}도 출력을 할 것인데... 0부터 Max까지 반복하면서 Select[i] = true인 놈들을

출력해버리면, 당연히 1이 가장 먼저 있기 때문에 {1,2,3}이 또 출력되게 될 것이다. 따라서 본인은 Vector를 사용해서

선택할 때마다, Vector에 넣어주고 빼주면서 Vector를 출력하는 방식으로 구현을 한다.

 

 

작동 과정

[ 현재 Cnt = 0 ]

0번째가 선택되어 있지 않으므로

Select[0]=true 로 바꿔주고 

Vector 0번째 값인 1을 넣어준다.

DFS(1);

 

[현재 Cnt=1 , i=0]

0번째가 선택되어 있으므로 지나가고

[현재 Cnt=1, i=1]

1번째가 선택되어 있지 않으므로 

Select[1]=true 로 바꿔주고

Vector 1번째 값인 2를 넣어준다.

DFS(2);

 

[현재 Cnt=2, i=0]

0번째, 1번째는 선택되어 있으므로 지나가고

[현재 Cnt=2, i=2]

2번째는 선택되어 있지 않으므로

Select[2]=true로 바꿔주고

Vector에 2번째 값인 3을 넣어준다.

DFS(3);

 

[현재 Cnt=3]

Print(); 가 실행된다.

Vector에 있는 값을 출력한다. 선택된 값들이 출력되는 것이므로 차례대로 1,2,3이 출력된다.

return되어 마지막으로 재귀가 호출됐던 위치로 돌아간다. 

 

[현재 Cnt=2, i=2]

2번째는 선택되어 있지 않으므로

Select[2]=true로 바꿔주고

Vector에 2번째 값인 3을 넣어준다.

DFS(3);

-------★ 도착

 

 

Vector에 있는 2번째 값인 3을 빼준다.

Select[2]=false로도 바꿔준다.

 

[현재 Cnt=2,i=3]

Select[3] 은 선택되어 있지 않으므로

Select[3]=true로 바꿔주고

Vector에 3번째 값인 4를 넣어준다.

DFS(3);

[현재 Cnt=3]

Print(); 가 실행된다.

Vector에 있는 값을 출력한다. 선택된 값들이 출력되는 것이므로 차례대로 1,2,4가 출력된다.

return되어 마지막으로 재귀가 호출됐던 위치로 돌아간다. 

 

 

[현재 Cnt=2,i=3]

Select[3] 은 선택되어 있지 않으므로

Select[3]=true로 바꿔주고

Vector에 3번째 값인 4를 넣어준다.

DFS(3);

-------★ 도착

Vector에 있는 3번째 값인 4를 빼준다.

Select[3]=false로도 바꿔준다.

 

[현재 Cnt=2, i=4]

Select[4] 는 선택되어 있지 않으므로

Select[4]=true로 바꿔주고

Vector에 4번째 값인 5를 넣어준다.

DFS(3);

[현재 Cnt=3]

Print(); 가 실행된다.

Vector에 있는 값을 출력한다. 선택된 값들이 출력되는 것이므로 차례대로 1,2,5가 출력된다.

return되어 마지막으로 재귀가 호출됐던 위치로 돌아간다. 

 

 

이제 이 아래 과정이 중요! 조합과 다른부분이 나타난다. 주의깊게 보자

 

[현재 Cnt=2, i=4]

Select[4] 는 선택되어 있지 않으므로

Select[4]=true로 바꿔주고

Vector에 4번째 값인 5를 넣어준다. 

DFS(3);  -------★ 도착

 

Vector에 있는 4번째 값인 5를 빼주고 Select[4]=false로 바꿔준다. -> 현재 Vector에는 1, 2 가 들어가있는 상태

[현재 Cnt=2, i=5] -> for문 조건에 맞지 않으므로 for문을 빠져나온다. 

return되어 마지막으로 재귀가 호출됐던 위치로 돌아간다.

 

 

[현재 Cnt=1 , i=0]

0번째가 선택되어 있으므로 지나가고

[현재 Cnt=1, i=1]

1번째가 선택되어 있지 않으므로 

Select[1]=true 로 바꿔주고

Vector 1번째 값인 2를 넣어준다.

DFS(3);  -------★ 도착

 

Vector에 있는 1번째 값인 2를 빼주고 Select[1]=false로 바꿔준다. -> 현재 Vector에는  1이 들어가있는 상태

 

[현재 Cnt=1, i=2]

2번째 값이 선택되어 있지 않으므로

Select[2]=true로 바꿔주고 Vector에 2번째 값인 3을 넣어준다. -> 현재 Vector에는 1,3 이 들어가있는 상태

DFS(2);

 

[현재 Cnt=2, i=0]

0번째가 선택되어 있으므로 지나가고

[현재 Cnt=2, i=1]

1번째가 선택되어 있지 않으므로

Select[1]=true로 바꿔주고

Vector에 1번째 값인 2를 넣어준다. -> 현재 Vector에는 1,3,2 가 들어가있는 상태

DFS(3);

[현재 Cnt=3]

Print(); 가 실행된다.

Vector에 있는 값을 출력한다. 선택된 값들이 출력되는 것이므로 차례대로 1,3,2가 출력된다.

 

 

 

(더 있는데 생략)