[백준] 15655- N과 M (6) [JAVA]

https://www.acmicpc.net/problem/15655

 

[정답]

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

public class Main {

    static int[] graph;
    static boolean[] visited;
    static int[] result;
    static int n;
    static int m;
    static void dfs(int idx, int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(result[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = idx; i < n; i++) {
            result[depth] = graph[i];
            dfs(i + 1, depth + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        graph = new int[n];
        for(int i=0; i<n; i++){
            graph[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(graph);
        visited =new boolean[graph.length];
        result =new int[m];
        dfs(0, 0);

    }
}

 

[풀이]

조건: N개의 자연수 중에서 M개를 고른 수열, 고른 수열은 오름차순

고른 수열이 오름차순이어야 하므로 처음에 입력을 받은 후에 오름차순으로 정렬 -> Arrays.sort (graph)

모든 조합을 한단계씩 확인하기 위해 dfs를 사용

m개의 수열을 찾아야 하기 때문에 depth가 m인 경우 수열을 출력

아닌 경우에는 

for문을 통해 idx+1로 계속 재귀호출한다

for (int i = idx; i < n; i++) { // 이전에 탐색한 수는 또 탐색하지 않도록 시작지점이 0이 아닌 idx로
            result[depth] = graph[i]; // 탐색한 수는 결과 배열에 저장
            dfs(i + 1, depth + 1); //재귀 호출하여 탐색
        }

 

이러한 과정으로 진행하여 탐색