백준 15649번 : N과 M(1)

백트래킹 문제의 가장 첫번째에 있는 문제. 매우 쉬울줄 알았으나, 생각보다 어려웠다. 백트래킹을 구현하는것 자체가 처음이니..

 

백트래킹이란?

깊이 우선탐색을 하는것 처럼 변수에 허용되는 값을 하나씩 대입서 조건을 만족하지 않을것 같은 경우 해당 경로는 가지 않고 전 노드로 돌아가는 기법이다. 따라서 반복의 횟수를 줄일수 있다. 

 

 

간단핟게 풀이를 설명하자면 출력할 수열의 길이를 가진 배열 하나와, 숫자의 사용여부를 표시하기 위한 배열을 하나만들고, 사용 여부 배열이 false인 index값을 출력할 배열에 입력하고 다시 메소드를 불러서 반복한다. 이때, 깊이가 출력할 수열의 크기가 같아지면 출력을 하고 전상태 노드로 돌아간다.

import java.util.Scanner;

public class Main {
    static int[] arr; //출력할 열
    static boolean[] bool_list; //중복을 피하기 위한 숫자 사용여부 배열

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n= scanner.nextInt();
        int m= scanner.nextInt();
        arr=new int[m];
        bool_list=new boolean[n];
        Main main=new Main();
        main.dfs(0);
    }

    public void dfs(int deep){
        if(deep==arr.length){
            for(int item: arr)
                System.out.print(item+" ");
            System.out.println();
            return;
        }
        for(int i=0;i< bool_list.length;i++){
            if(!bool_list[i]) {
                arr[deep] = i + 1;
                bool_list[i]=true;
                dfs(deep+1);
                bool_list[i]=false;
            }
        }
    }

}