[인프런/DFS/9.조합구하기] - 정 리 중 -

<<풀이>>

 

일단 내가 생각한 논리대로 진행을 했는데 어디선가 막힌 것 같다 ㅋㅋ ㅠ

 

아마 중간에 놓쳤거나 실수한 부분이 있을 것이라고 본다.

 

어떤 논리로 움직이는지 파악은 되지만 여전히 헷갈리는 DFS ㅜㅡㅜ

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static int[] ch;
    static ArrayList<Integer> list = new ArrayList<>();

    private void DFS(int L, int i, int n, int m) {

        if (L == m) {
            for (int x : list) {
                System.out.print(x + " ");
            }
            list.clear();
            return;
        }

        if (ch[i] == 1) return;
        else {
            ch[i] = 1;
            list.add(i);

            for (int j = 1; j <= n ; j++) {

                DFS(L+1, j, n, m);
                ch[i] = 0;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] arr = br.readLine().toCharArray();
        int n = Integer.parseInt(String.valueOf(arr[0]));
        int m = Integer.parseInt(String.valueOf(arr[2]));
        ch = new int[n+1];

        for (int i = 1; i <= n; i++) {
            T.DFS(0, i, n, m);
        }
    }
}

 

 

-강사님 풀이-

 

와 .. 정말 신기하게 풀었다.'

 

강사님 왈 " 이 풀이는 그냥 외우는게 좋다!! "

 

일단 어떤 원리인지는 깨달았다. 조금 있다가 최종 마무리 하겠다.

import java.util.*;
class Main{
    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);
    }
}