[Inflearn] 조합구하기(DFS) (c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

위키백과에서 조합은

조합론에서 조합(combination)은 집합에서 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. 그 경우의 수는 이항계수이다.

라고 정의되어 있다.

순서에 상관없이 뽑을 수 있다고 하였고, 중복이 되면 안되므로,

n = 6, r = 4 로 입력되었을 때,

아래와 같이 DFS 구조를 그릴 수 있다.

외계인친구를 데려와봤다..

DFS의 전형적인 특징은 다리의 개수만큼 모두 동작해야한다는 것이다.

즉 모든 다리가 다 사용되어야 한다.

초기 D(0, 0)로 재귀함수가 호출되면

0, 1, 2, 3, 4, 5 일 경우가 모두 탐색되어야 한다.

먼저 0이 사용되었을 경우,

lv = 1

0

그 다음 사용 가능한 자연수는

1, 2, 3, 4, 5 가 된다.

여기서도 1을 먼저 사용해보자.

lv = 2

0

1

그 다음 사용 가능한 자연수는

2, 3, 4, 5 가 된다.

여기서도 2를 먼저 사용해보자.

lv = 3

0

1

2

그 다음 사용 가능한 자연수는

3, 4, 5 가 된다.

여기서도 3을 먼저 사용해보자.

lv = 4

0

1

2

3

level이 4가 되었으므로 

선택된 자연수를 출력해준다.

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int n, r, cnt = 0, ch[20];
 
void DFS(int s, int L)
{
    int i;
 
    if (L == r)
    {
        for (i = 0; i < r; i++)
        {
            printf("%d ", ch[i]);
        }
 
        puts("");
        cnt++;
    }
    else
    {
        for (i = s; i < n; i++)
        {
            ch[L] = i;
            DFS(i + 1, L + 1);
        }
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    scanf("%d %d", &n, &r);
    
    DFS(0, 0);
 
    printf("%d\n", cnt);
 
    return 0;
}

line 43) 초기 DFS() 호출 시, 시작 자연수 0, 레벨 0 을 인자로 넘겨준다.

line 13~35) 시작 자연수(start)와 L(level) 을 매개변수로 받는다.

line 17~26) 재귀함수의 종료 조건은 L == r 일 경우, 즉 뽑으려는 자연수를 모두 뽑았을 때이다.

    재귀함수가 종료되기 전 뽑힌 자연수를 보여주고, 조합의 개수를 구하기 위해 cnt++

line 27~34) 시작 자연수부터 n까지 반복하는데, 해당 자연수를 사용할 경우 check[] 배열에 넣어주고

               DFS() 함수에 사용한 자연수 + 1, Level + 1 을 인자로 넘겨준다.

조합은 많은 문제에서 사용된다고 하니 그냥 코드를 외워두는게 좋다고 한다.

머릿속에 입력해두자!

#. Result

  - Input --------------------------------------------------------

6 4

------------------------------------------------------------------

  - Output --------------------------------------------------------

0 1 2 3

0 1 2 4

0 1 2 5

0 1 3 4

0 1 3 5

0 1 4 5

0 2 3 4

0 2 3 5

0 2 4 5

0 3 4 5

1 2 3 4

1 2 3 5

1 2 4 5

1 3 4 5

2 3 4 5

15

------------------------------------------------------------------