[백준 풀이_Java] 15649 N과 M (1) (실버3)

 

백트래킹 푸는 꿀Tip!

 

* 백트래킹은 트리구조를 떠올린 후 시작한다.

* 주어지는 숫자의 범위가 작다.

* 재귀함수 사용 시 종료 시점을 파악한다.

 

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

public class Main {
    static int N;
    static int M;
    static boolean[] visited;
    static ArrayList<Integer> answer;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        visited = new boolean[N+1]; // 0번째는 사용 안하고
        answer = new ArrayList<Integer>();

        backTrackingFunction(N, 0);

    }
    static void backTrackingFunction(int limit, int length){// 사실 limit 파라미터는 없어도됨

        if(length == M){
            for(int i=0; i<length; i++){
                System.out.print(answer.get(i) + " ");
            }
            System.out.println();
            return;
        }

        for(int i=1; i<N+1; i++){
            if(visited[i]) continue;

            visited[i] = true; // 방문 체크
            answer.add(i);
            backTrackingFunction(limit, length+1);
            // 이 지점이 하나의 백트래킹을 완료한 시점.

            visited[i] = false; // 마지막 방문 해제
            answer.remove(answer.size()-1);

        }
    }

}