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

Fxcking Backtracking

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

15650번: N과 M (2)

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 13단계

 

백트래킹의 카테고리에 포함되어 있는 문제이다.

 

이전의 15649번 문제인 N과 M (1)의 문제와 비슷한 문제이다.

 

(1)은 모든 경우를 출력하였다면,

 

(2)는 오름차순의 경우에만 출력하는 문제이다.

 

나는 기존의 코드에서 다음 재귀를 호출하기 전 출력하려는 배열에

 

오름차순이 저장되어 있다면 다음을 호출하는 방식으로 문제를 해결하였다.

 

import java.util.Scanner;

public class Question_15650 {
	static boolean[] visit = new boolean[10];
	static int[] Output = new int[10];
	
	static void Backtracking(int index, int N, int M) {
		if(index == M) {
			for(int i = 0; i < M; i++) {
				System.out.print(Output[i]);
				if(i != M)
					System.out.print(' ');
			}
			System.out.println();
		}
		for(int i = 1; i <= N; i++) {
			if(visit[i]) {
				continue;
			}
			visit[i] = true;
			Output[index] = i;
			if(index == 0)	//처음 수의 경우 비교 대상이 없으니 다음단계로 넘어감
				Backtracking(index + 1, N, M);
			if(index > 0 && Output[index] > Output[index - 1]) {
            // 배열에 저장되어 있던 수와 비교하여 오름차순이 아닐경우 실행되지 않음
				Backtracking(index + 1, N, M);
			}
			visit[i] = false;
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		Backtracking(0, N, M);
	}
}