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

 

# 문제설명

 N과 M(1) 과 같은 dfs 문제이다. (1)번 문제와는 다르게 오름차순을 만족해야 한다.

 

 마찬가지로 노드들에 대한 탐색을 진행하면서 조건에 맞는 노드들만 탐색한다.

 

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

 

# 코드구현

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

public class Main{
    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);


    }
}