N과M(백준 15649) - 백트래킹

문제 문석

1. 가능한 선택지 탐색 (1,2,3,4)
   • 작은 수부터 탐색 -> 사전순 출력 조건 만족
2. 유효성 검사 및 가지치기
   • 같은 수는 여러번 사용할 수 없기 때문

정답

package A0study;

import java.util.Scanner;

public class p15649_N과M {
    static int N, M;
    static int[] S;         // 수열
    static boolean[] V;     // 숫자 사용 여부

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();   // 1~N
        M = sc.nextInt();   // 뽑을 개수
        S = new int[N];
        V = new boolean[N];

        backtracking(0); // 길이 0부터 시작
    }

    private static void backtracking(int length) {
        // 정답확인
        if(length == M) {
            // 수열 출력
            printArray();
            return;
        }

        // 갈 수 있는 선택지 탐색
        for(int i=0; i<N; i++) {
            // 가지치기
            if(!V[i]) { // 아직 사용하지 않은 숫자라면
                V[i] = true;
                S[length] = i; // 현재 자리 채우기
                backtracking(length + 1); // 다음 자리로 이동
                V[i] = false; // 다른 경우를 위해 숫자 사용 해제
            }
        }
    }

    private static void printArray() {
        for(int i=0; i<M; i++) {
            System.out.print(S[i] + 1 + " "); // +1 해서 실제 숫자
        }
        System.out.println();
    }
}