백준 15649: N과 M (1) (java)

 

재귀가 좀 헷갈려서 그림을 그렸더니 훨씬 이해가 잘 되더라!

이전에 알고리즘 수업 들었을 때, 수열 관련 문제로 이게 나왔었는데 다시 보니 반가웠다.

 

바킹독님의 백트래킹 강의를 보면서 공부했는데..

원래 나동빈님 이코테 보다가 바킹독님 강의 보니까 문제 난이도가 확실히 어렵다 ;; ㅜ

 

기초 잡기엔 나동빈님 문제가 좋은 것 같고,

응용하기엔 바킹독님 문제랑 풀이가 좋은 것 같아서 둘 다 잡고 갈 예정!

 

대신 커리(?)는 바킹독님 강의를 메인으로 따라갈 것 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ15649 {
    int N, M;
    int[] arr = new int[10];
    boolean[] isUsed = new boolean[10];

    public void func(int k) {
        // 수열이 완성된 경우
        if (k == 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 (!isUsed[i]) { // 특정 숫자가 사용되지 않았다면
                arr[k] = i;
                isUsed[i] = true;
                func(k+1);

                isUsed[i] = false; // 재귀 호출이 끝나면 i번째 수의 사용 여부를 원상 복귀
            }
        }
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken()); // 끝 숫자
        M = Integer.parseInt(st.nextToken()); // 수열 길이

        // 상태 공간 트리 0으로 시작
        func(0);
    }

    public static void main(String[] args) throws Exception {
        new BOJ15649().solution();
    }
}