[백준] 15649번 N과 M (1) - Java[백트래킹]

[백준] 15649번 N과 M (1) - Java

 

문제 출처

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

15649번: N과 M (1)

 

---

※ 풀이

문제에서 준 수의 범위가 크지 않으므로 브루트포스로 재귀적으로 푸는 문제이다.

각 수를 사용 했는지 안했는지 체크해주면서 해당 수를 고르거나 고르지 않으면 된다

(해당 내용은 재귀함수 내에서 구현)

 

 

 

 

 

 

---

※ 소스코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] data = new int[m];
        boolean[] isUsed = new boolean[n + 1];
        Arrays.fill(isUsed, false);

        process(n, m, 0, data, isUsed);
    }

    static void process(int n, int m, int index, int[] data, boolean[] isUsed) {
        if (index == m) {
            //print
            StringBuilder stb = new StringBuilder();
            for (int i = 0; i < data.length; i++) {
                stb.append(data[i]);
                if (i < data.length - 1) {
                    stb.append(" ");
                }
            }
            System.out.println(stb);
        } else {
            for (int i = 1; i <= n; i++) {
                if (isUsed[i]) continue;
                isUsed[i] = true;
                data[index] = i;
                process(n, m, index + 1, data, isUsed);
                isUsed[i] = false;
            }
        }
    }
}