[Algorithm_Java] 15652번 N과 M (4) (Success)

15652번: N과 M (4)

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();
 
    public static int N, M;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[M];
        dfs(1, 0);
 
        br.close();
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
    public static void dfs(int idx, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
 
        for (int i = idx; i <= N; i++) {
            arr[depth] = i;
            dfs(i ,depth + 1);
 
        }
    }
}
 

🤔 해설

1. arr = new int[M];

    - 출력을 위한 arr 배열 생성

2. dfs(1, 0);

    - dfs(방문 시작점, 배열 내 위치)

3. for (int i = idx; i <= N; i++) {

    - i를 idx부터 시작함으로써 다음 depth에서 시작점보다 작은 값을 방문하지 않도록 함

4. arr[depth] = i;

    - 배열 내 현재 위치에 값 입력

5. dfs(i, depth + 1);

    - 깊은 노드로 이동

 

 

 

🔗 소스 코드
GitHub