[백준 15649번] 백트래킹 기본 1

문제 링크: 15649번 N과 M (1)

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

 

1부터 n까지의 숫자 중 방문하지 않은 숫자에 대해서 방문 처리를 하고, 그 숫자를 길이가 m인 arr의 depth에 해당하는 자리에 저장해준다. 그리고 depth를 증가시켜 또 다른 방문하지 않은 숫자에 대해서 이러한 과정을 반복한다.

depth가 1부터 시작한다고 하면, depth는 지금 몇 번째 깊이의 숫자를 고르고 있느냐에 대해서 나타낸다. 즉 depth == m까지 계속해서 증가해야 하고, depth > m일 때 arr는 출력되며, 그 뒤의 경우는 promising하지 않으므로 return한다.

 

import java.util.Scanner;

public class Main {	
	public static int[] arr;
	public static boolean[] visit;
	
	public static void print(int[] arr) {
		StringBuilder sb = new StringBuilder();
		
		for (int i = 1; i < arr.length; i++) {
			sb.append(arr[i]).append(' ');
		}
		System.out.println(sb);
	}
	
	public static void select(int n, int m, int depth) {
		if (depth > m) {
			print(arr);
			return;
		}
		
		for (int i = 1; i <= n; i++) {
			if (!visit[i]) {
				visit[i] = true;
				arr[depth] = i;
				select(n, m, depth+1);
				visit[i] = false;
			}
		}
	}
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        arr = new int[m+1];
        visit = new boolean[n+1];
        
        select(n, m, 1);
        
        sc.close();
    }
}