[문제풀이] 08-09. 조합 구하기

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0809. 조합 구하기(DFS)

🗒️ 문제

🎈 나의 풀이

	private static int n, m;
    private static void DFS(int i, int j, String str) {
        if(i == m) {
            System.out.println(str);
            return;
        }

        for(int k=j; k<=n; k++) {
            String marbles = str;
            marbles += k + " ";
            DFS(i+1, k+1 , marbles);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        DFS(0 , 1, "");
    }

🖍️ 강의 풀이

  	static int[] combi;
	static int n, m;
	public 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);
			}
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		combi=new int[m];
		T.DFS(0, 1);
	}

💬 짚어가기

해당 문제는 DFS를 이용하여 풀 수 있다. 이미 사용한 숫자를 체크하는 배열을 두고
반복문을 통해 1부터 n까지 체크 배열에 넣어가며 사용할 수 있는 숫자를 줄여간다.

반복문 내에서 재귀 호출을 수행할 때, 파라미터로 현재의 인덱스를 넘기도록 하여 호출된
메서드에서 반복문이 그 다음 인덱스부터 순회할 수 있도록 한다.