[백준] 15650 N과 M (2) (JAVA)

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

15650번: N과 M (2)

풀이 

 이 문제는 저번에 풀었던 N과 M (1)문제에서 오름차순이 추가되었다는것을 제외하고는 전부 동일하다. 그래도 다시한번 더 설명을 해놓을테니 혹시라도 이러한 문제를 처음풀거나 여전히 어려운 사람들은 보기 바란다.

 

 이 문제는 DFS와 비슷한 백트래킹을 사용한다. 여기서 백트래킹이 무엇이냐 하면 유망하지않은 노드는 선택하지 않는다는것이다. 예를 들어 이번에 포스팅하는 문제를 예시로 들어 설명을 하면 수열에 존재하는 조건이 두가지가 있다.

하나는 중복된 수가 있어서는 안된다는것이고 두번쨰는 오름차순이 되어야 한다는 것이다. 그렇다면 만약 수열의 수들이 하나라도 중복된수가 있다거나 혹은 하나라도 내림차순이 되어있다면 이는 뒤에 무슨 답이 오든 틀린 답이 된다. 그렇다는 것은 유망하지않는다는것이고 이는 곧 연산을 해도 쓸모가 없다는 것이다. 무슨말인지 알겠는가? 예들 들면 2-3까지 선택이 되어있다고 가정하고 다음번에 1이 와서 수열은 2 - 3 - 1이 되어 오름차순이라는 조건을 불만족한다 그러면 2 - 3 - 1 뒤에는 무엇이 오든 틀린답이 된다. 보다 자세한 내용은 코드를 보면 이해가 갈것이다.

 

코드

import java.io.*;
import java.util.StringTokenizer;

class Main{

    public static int N;
    public static int M;
    public static int []arr;
    public static boolean [] visit;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());

        arr = new int[M];
        visit = new boolean[N];

        DFS(0);
        bw.flush();
        bw.close();
    }

    public static void DFS(int depth) throws IOException {
        if(depth  == M) {
            for(int val : arr) {
                bw.write(String.valueOf(val + " "));
            }
            bw.write("\n");
            return;
        }

        for(int i=0; i<N; i++){
            if(!visit[i] && (depth ==0 ||arr[depth-1] < i+1)) {
                visit[i] = true;
                arr[depth] = i+1;
                DFS(depth + 1);
                visit[i] = false;
                arr[depth] = -1;
            }
       }
    }
}