[백준] 15666번 : N과 M (12) - JAVA [자바]

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

DFS 알고리즘 문제이다.

총 M 깊이의 그래프를 dfs로 탐색하면 된다.

1. 같은 수를 여러번 사용해도 되므로 visited 배열로 방문했는지 검사할 필요가 없다.
2. 비내림차순 즉, 전에 고른 숫자와 같은 수부터 탐색하면 되므로 전에 고른 수의 index를 같이 넘겨줘서 넘겨받은 index 부터 탐색한다.
3. 중복되는 수열은 출력하면 안되므로 정답을 담는 배열을 집합(Set)사용하며 순서가 있으므로 LinkedHashSet 을 사용

public class bj15666 {

    public static boolean[] visited;
    public static int[] numArr;
    public static int[] nArr;
    public static Set<String> set = new LinkedHashSet<>();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();
        String[] split = line.split(" ");
        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);

        String line1 = br.readLine();
        String[] split1 = line1.split(" ");
        nArr = new int[N];
        for (int i = 0; i < N; i++) {
            nArr[i] = Integer.parseInt(split1[i]);
        }
        Arrays.sort(nArr);

        numArr = new int[M];
        visited = new boolean[N];

        dfs(0, 0, N, M);

        for (String str : set) {
            bw.write(str + "");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int index, int depth, int n, int m) {
        if (depth == m) {
            String str = "";
            for (int number : numArr) {
                str += number + " ";
            }
            set.add(str + "\n");

            return;
        }
        for (int i = index; i < n; i++) {
            numArr[depth] = nArr[i];
            dfs(i, depth + 1, n, m);
        }
    }
}