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

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

 

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

public class Main {
    static int n, m;
    static int[] arr;       // 출력할 수열을 담을 배열(길이가 m인 수열)
    static boolean[] chk;   // 재귀함수에서 1~n까지 자연수의 방문 여부를 확인 할 배열
    static StringBuilder result = new StringBuilder();
    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());

        arr = new int[m+1];     // 길이가 2인 수열일 경우 arr[1]과 arr[2]에 수열을 저장하도록 m+1 길이의 배열로 선언
        chk = new boolean[n+1]; // 1~n까지 자연수의 방문 여부를 체크할 때, n에 대한 방문여부를 chk[n]로 확인 할 수 있게끔 n+1 길이의 배열로 선언

        recur(1);   // 깊이를 1부터 시작하여 1부터 탐색하도록 함.

        System.out.println(result);
    }
    public static void recur(int depth) {
        // 재귀 호출을 멈추는 조건 : 재귀 깊이가 m보다 커진 경우
        if (depth > m) { 
            // j는 1~m까지 수열 길이만큼 반복 실행
            for (int j=1; j<=m; j++) {
                result.append(arr[j]).append(" ");
            }
            result.append("\n");
            return;
        }

        // i는 1~n까지 반복 실행
        for (int i=1; i<=n; i++) {
            // i에 방문하지 않은 경우
            if (!chk[i]) {
                // 방문여부 true로 변경하고, 수열에 값 추가 및 재귀 호출
                chk[i] = true;
                arr[depth] = i;
                recur(depth+1);

                // 재귀 호출을 끝내고 돌아오면 다시 방문하지 않은 상태로 변경
                // -> [1, 2] 수열로 2는 이미 방문했지만, 이후 [2, 1] 등에 다시 방문해야 하므로
                chk[i] = false;
            }
        }
    }
}