[Algorithm] 조합 구하기(DFS)

설명

1부터 N까지 번호가 적힌 구슬이 있습니다. 

이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

 

출력

첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.

 

예시 입력 / 출력

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

 

 

풀이 과정.

조합의 수와 조합 자체를 구하는 방식이 다르다.

문제에서는 조합의 수라고 하였지만 출력 예시는 조합 자체이다.

n개의 정수에서 m개를 뽑는 조합을 나열한다. (중복X, 순서와 위치 상관X)

 

우선 입력을 받고 처음 DFS()함수의 매개변수로 0과 1을 넣어서 호출한다.

0은 level(l)이고, 1은 시작번호(s)로 사용할 것이다.

 

우선 재귀함수 내부 if else 조건으로 if에는 level이 m일 때 retun한다.

이제 else 작업을 해준다.

여기서 중요한건 s의 사용 용도 이다.

s는 반복문의 시작 index로 주어 반복문 내의 재귀함수를 탈 때마다 반복횟수가 줄어들게 만든다.

 

예를들어 n개의 정수 4개중 2개를 뽑는다(4C2)고 가정하고 반복하게 되면

1, 2, 3, 4 반복 하면서 다음 재귀함수 같은 반복문 안에서 시작 인덱스는 2, 3, 4

2, 3, 4 반복 하면서 다음 재귀함수 같은 반복문 안에서 시작 인덱스는 3, 4

 

여기서 해당 level에서 배열에 값이 담기는 과정을 보자.

0 level 에서 배열[해당 level] = 시작 인덱스 값 (1)

1 level 에서 배열[해당 level] = 시작 인덱스 값 (2, 3, 4)

2 level 에서 배열에 담긴 값 출력 - 1 2 / 1 3 / 1 4

 

0 level 에서 배열[해당 level] = 시작 인덱스 값 (2)

1 level 에서 배열[해당 level] = 시작 인덱스 값 (3, 4)

2 level 에서 배열에 담긴 값 출력 - 2 3 / 2 4

 

0 level 에서 배열[해당 level] = 시작 인덱스 값 (3)

1 level 에서 배열[해당 level] = 시작 인덱스 값 (4)

2 level 에서 배열에 담긴 값 출력 -  3 4

 

1 2 / 1 3 / 1 4 / 2 3 / 2 4 / 3 4 총 6개의 조합이 나온다.

이렇게 원소들의 순서와 위치에 상관없이 중복을 배제하면서 값을 만들 수 있다.

 

 

풀이.

public class Main {

    static int n; // n개의 정수에서
    static int m; // m개를 뽑는다.
    static int combi[]; // 각 조합을 담을 배열

    static void DFS(int l, int s){
        if(l == m){
            for(int x : combi) System.out.printf(x+" ");
            System.out.println();
        }else{
            for (int i = s; i <= n; i++) { // s는 시작 index
                // 조합배열 combi[해당레벨l] = i(시작번호s)
                combi[l] = i;
                DFS(l+1,i+1); // l 1 증가, i 1증가
            }
        }
    }
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        combi = new int[m];
        DFS(0,1);
    }
}

 

---

 

정리 :

조합 구하는 공식으로 생각하고 외워버리는게 더 편할 듯 싶다.