[백준] 15649번 : N과 M (1)(JAVA)

어려운 백트래킹

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

15649번: N과 M (1)

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

 

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

 

아직 나에게 있어 백트래킹은 어려운 알고리즘이라서

 

구글링을 통해 검색하고 코드를 보고 공부하여 문제를 해결하였다.

 

좀더 공부하고 쓰면서 단계를 이해하여야겠다.

 

import java.util.Scanner;

public class Question_15649 {
	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-1)
					System.out.print(' ');
			}
			System.out.println();
			return;
		}
		
		for(int i = 1; i <= N; i++) {
			if(visit[i]) {
				continue;
			}
			visit[i] = true;
			Output[index] = i;
			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);
	}
}