BOJ - N과 M (4)

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

15652번: N과 M (4)

 

• 단계별 풀어보기 - 백트렉킹 문제이다.
  • https://www.acmicpc.net/step/34 
  • 비내림차순 조건 만족 시에만 다음 방문을 진행하면 통과

 

package baekjoon;

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++) {
            Integer next = i;

            //방문 노드와 이전 노드간 비내림차순 조건
            if (!numbers.isEmpty()) {
                Integer integer = numbers.get(numbers.size() - 1);
                if (next < integer) {
                    continue;
                }
            }
            numbers.add(next);

            dfs(numbers, visited, depth + 1);
            //중복으로 값이 들어가므로 가장 멘 뒤에 노드를 삭제한다.
            numbers.remove(numbers.size() - 1);
        }
    }
}