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

• 백트래킹 입문 문제 2
  https://www.acmicpc.net/problem/15650

1. 문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

2. 문제 접근

1) N의 수가 충분히 적고 M의 길이가 계속 달라지기 때문에 백트래킹 알고리즘을 적용한다.
2) 중복이 되면 안되기 때문에 중복을 체크하는 boolean 배열을 하나 사용하고 수열을 저장하는 int형 배열을 하나 사용한다.
3) 백트래킹 알고리즘에서 boolean 배열을 체크하고 전에 나온적이 없고 바로 이전의 수가 현재 수보다 작은 경우에만 수를 저장한다.
4) 모든 경우의 수를 다 탐색한다.

3. 코드

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

public class b_15650 {
    static int N,M;
    static boolean check[];
    static int num[];
    static StringBuilder sb = new StringBuilder();
    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());

        int depth = 0;
        check = new boolean[N+1];
        num = new int[N];
        back(depth);
        System.out.print(sb);
    }

    static void back( int depth){
        if(depth == M){
            for(int i=0;i<M;i++){
                sb.append(num[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=1;i<=N;i++){
            if(!check[i]){
                if(depth ==0 || (depth>0 && num[depth-1] < i)){
                    num[depth] = i;
                    check[i] = true;
                    back( depth +1);
                    check[i] = false;
                }
            }
        }
    }
}