[백준 15649] N과 M (1)

백트래킹 공부를 하면서, 내가 그 동안 어려워했던 문제들이 백트래킹 문제라는 것을 알게 되었다..
백트래킹이란 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.

문제 설명

문제 링크
참고 링크
(해당 참고 링크가 백트래킹에 대한 정리가 너무너무 잘 되어있다 !
*해당 문제는 참고 링크를 통해 생각 정리와 코드를 완성할 수 있었다.)

생각 정리

//백트래킹을 위한 함수를 호출한다. 
//함수 내에서
//고른 수의 개수 == M이라면 (끝까지 탐색했다면)
	//M개의 수열을 출력하고 리턴한다.
//그 외에는 (끝까지 탐색한 것이 아니라면)
	//1 ~ N 까지 반복하며 아직 쓰이지 않은 수를 찾아낸다. 
    	//아직 쓰이지 않았다면 (false라면)
        	//해당 숫자를 사용한다. (true로 바꾼다.)
            //수열의 배열에 해당 숫자를 넣는다.
            //고른 수의 개수+1을 파라미터로 다시 해당 함수를 호출한다. (재귀)
            //해당 숫자를 사용하지 않음으로 나타낸다. (재귀함수에서 리턴이 되었다면 이전 상태로 되돌아옴을 의미한다. false로 되돌려 해당 idx가 쓰이지 않음을 나타낸다.)

깊이 탐색과 백트래킹이 비슷하다는 생각을 했다.

(참고 링크에서 해당 궁금증에 대한 대답도 찾을 수 있었다!)

완성

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static boolean[] visited;
    static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N+1];
        arr = new int[M+1];

        func(0);
    }

    static void func(int current) {
        if(current == M) {
            for(int i=0; i<M; i++)
                System.out.print(arr[i] + " ");
            System.out.println();
            return ;
        }

        for(int i=1; i<=N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[current] = i;
                func(current + 1);
                visited[i] = false;
            }
        }
    }
}