[Dev-Ping9] 백준 15649번 - N과 M (4) (Java) [DFS]

 

# 문제 설명

 N과 M 시리즈 마지막 문제이다. 

 (3)번과 다르게 비내림차순이여야 한다.

 

 DFS를 처음 접근하시는분들께 좋은 연습문제시리즈인 것 같다.

 

 ** if 문의 or 절은 앞의 조건이 참일 시, 뒤의 조건을 검사하지않는다. (idx-1 이 OutOfArrayIndex Exception을 발생시키지 않음.)

 

 

# 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class test{
    static boolean[] picked;
    static int[] space;
    static StringBuilder sb = new StringBuilder();
    static void dfs(int idx, int nodeEnd,int limit){
        if(idx == limit){
            // printArr(space);
            for(int num:space){
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=1; i<=nodeEnd;i++){
            if(!picked[i]){
                // picked[i]=true;
                if(idx == 0 || space[idx-1]<=i){
                    space[idx]=i;
                    dfs(idx+1,nodeEnd,limit);
                }
                // picked[i]=false;
            }
        }

        
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        picked = new boolean[n+1];
        space = new int[m];        
        dfs(0,n,m);
        System.out.print(sb);


    }
}