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

 

# 문제설명

 dfs 문제이다. 모든노드를 탐색하면서 조건에 도달할 시 출력해주면 된다.

 

 *StringBuilder 와 Sysout 의 성능차이는 어마어마하다.

 

 

# 코드 구현

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;
                space[idx]=i;
                dfs(idx+1,nodeEnd,limit);
                picked[i]=false;
            }
        }

        
    }
    static void printArr(int [] arr){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    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);


    }
}