BOJ - N과 M (2)

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

15650번: N과 M (2)

• 단계별 풀어보기 - 백트렉킹 문제이다.
  • https://www.acmicpc.net/step/34 
  • 노드 추가 전 이전 노드와 비교하여 오름 차순 일때 만 추가 탐색을 진행하면 통과 할 수 있다.

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


public class Main {

    public static int N;
    public static int M;

    public static StringBuilder builder = new StringBuilder();

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        ArrayList<Integer> numbers = new ArrayList<>();
        boolean[] visited = new boolean[N + 1];
        dfs(numbers, visited, 0);
        System.out.println(builder);
    }

    private static void dfs(ArrayList<Integer> numbers, boolean[] visited, int depth) {
        if (depth == M) {
            for (Integer no : numbers) {
                builder.append(no + " ");
            }
            builder.append("\n");
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (visited[i] == false) {
                Integer next = i;

                if (numbers.size() > 0) {
                    Integer prev = numbers.get(depth - 1);
                    if (prev > next) {
                        continue;
                    }
                }
                visited[i] = true;
                numbers.add(next);

                dfs(numbers, visited, depth + 1);
                visited[next] = false;
                numbers.remove(next);
            }
        }
    }
}