[PS] 인프런 강의 - DFS 9. 조합 구하기

 

문제

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

 

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

 

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

 

▣ 입력예제 1
4 2

 

▣ 출력예제 1
1 2
1 3
1 4
2 3
2 4
3 4

 

풀이

 

조합의 경우의 수를 출력해야하므로 다음과 같은 중복을 피해야 한다.

 

• 2 3, 3 2
• 1 1, 2 2 

 

이 경우는 ch 배열을 선언해서 방문 상태를 저장하면 1 1, 2 2 같은 중복은 피할 수 있겠지만 2 3, 3 2가 해결이 안된다.

 

DFS 함수 파라미터에 자연수 순회를 시작할 숫자를 넘겨주면 된다. (반복문을 시작하는 s값을 i+1로 넘겨줘서 다음엔 i+1 부터 순회하도록)

 

 

 

코드

import java.util.Scanner;

public class Main {
	
	static int n, m;
	static int[] combi; //pm같은 역할
	
	public static void DFS(int L, int s) {
		if(L == m) {
			for(int x : combi) System.out.print(x + " ");
			System.out.println();
		}
		else {
			//구슬 순회
			for(int i=s; i<=n; i++) {
				combi[L] = i;
				DFS(L+1, i+1); //주의: 다음엔 i+1부터 순회하도록
			}
		}
	}
 
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt(); //3~10
        m = in.nextInt(); //2~N
        
        combi = new int[m];
        
        DFS(0,1);
        
    }
}