[Algorithm] 조합 구하기(DFS)

❐ 조합 구하기

▶︎ 문제

   1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.
   자연수 N과 M이 입력됩니다. 

 

▷ 입력 예제

4 2

 

▶︎ 출력 예제

1 2
1 3
1 4
2 3
2 4
3 4

 

▷ 문제설명

조합은 서로 다른 n개의 원소를 가진 집합에서 순서에 상관없이 r개의 원소를 선택하는 것을 말한다. 

쉽게 말해 1부터 n까지 적혀있는 구슬 주머니에서 r개의 원소를 한번에 뽑는 경우의 수를 세는 것과 같다. 구슬을 뽑는 순서도 고려하는 순열과는 다르다. 

 

문제처럼 자연수 4까지의 수에서 2개를 뽑는 경우의 수를 그림으로 도식화하면 다음과 같다.

총 2개를 뽑는데 숫자 1은 무조건 포함되어 있는 경우의 수는 3개, 숫자 2는 무조건 포함되어있고 앞선 조합과 겹치치 않는 경우의 수는 2개, 숫자 3은 1개, 숫자 4는 없다. 

조합에서 1-2와 2-1은 같은 것이므로 또 다시 카운트할 필요가 없고, 이에 따라 탐색하는 for문의 시작변수는 계속 커진다. 

 

▶︎ 내 답안

function solution(n, m) {
    let answer = [];
    let tmp = Array.from({ length: m }, () => 0);
    function DFS(N, s) {
        if (N === m) {
            answer.push(tmp.slice());
        } else {
            for (let i = s; i <= n; i++) {
                tmp[N] = i;
                DFS(N + 1, i + 1);
            }
        }
    }
    DFS(0, 1);
    return answer;
}

console.log(solution(4, 2));

 

for (let i = s; i <= n; i++) {
    tmp[N] = i;
    DFS(N + 1, i + 1);
}

DFS 함수에서 사용되는 변수 s가 핵심이다. s는 'start'를 나타내는 단어로, 탐색을 시작할 인덱스의 번호를 담는 변수이다. s는 단계를 나타내는 변수 L이 변경될 때마다 함께 변경된다. s의 숫자가 커진다는 것은 탐색할 숫자가 적어진다는 뜻이 되는데, 이는 조합의 특성을 생각하면 당연한 결과다. 

코드가 동작하는 과정을 그림으로 도식화하면 다음과 같다.