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

🚀 문제 분석

• 목표: $1$부터 $N$까지의 자연수 중에서 중복 없이 $M$개를 고른 수열을 모두 구합니다.
• 핵심: '중복 없음'과 '순서가 다르면 다른 수열'이라는 조건은 전형적인 순열 문제입니다.
• 전략: 모든 경우의 수를 탐색하되, 이미 선택한 숫자는 건너뛰는 백트래킹(Backtracking)을 사용합니다.

💡 해결 전략: 유망한 경로만 탐색하기

백트래킹의 묘미는 "가보고 아니면 되돌아오는 것"입니다.

1. 방문 배열 (used): 현재 경로에서 어떤 숫자를 사용 중인지 기록하여 중복 선택을 방지합니다.
2. 상태 관리 (Deque): 현재 선택한 숫자들을 순서대로 저장합니다.
3. 재귀 호출: 다음 숫자를 선택하기 위해 깊이($k$)를 1 증가시켜 재귀 호출합니다.
4. 복구 (Backtrack): 재귀가 끝나고 돌아오면, 방금 선택했던 숫자를 Deque에서 제거하고 used 상태도 false로 되돌려 다른 경로에서 해당 숫자를 쓸 수 있게 합니다.

💻 구현 코드 (Java)

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

public class Main {
    static boolean[] used;
    static Deque<Integer> dq = new ArrayDeque<>();
    static int n, m;
    static final StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        // ... (입력 로직 생략)
        used = new boolean[n + 1];
        backtrack(0);
        System.out.print(sb);
    }

    static void backtrack(int k) {
        // M개를 모두 골랐다면 결과 저장 (Base Case)
        if (k == m) {
            for (int e : dq) sb.append(e).append(" ");
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!used[i]) { // 사용하지 않은 숫자라면
                used[i] = true;     // 1. 상태 결정
                dq.addLast(i);      
                
                backtrack(k + 1);   // 2. 다음 단계로
                
                dq.pollLast();      // 3. 상태 복구 (Backtrack)
                used[i] = false;
            }
        }
    }
}

🧐 기술적 고찰

• Deque vs int[]: 보통은 결과용 배열 ans[m]을 선언해서 인덱스로 관리하지만, Deque을 사용하면 add/poll 직관성이 높아져 로직 흐름을 파악하기 좋습니다.
• 시간 복잡도: $N$개 중 $M$개를 고르는 순열은 $_NP_M$의 경우의 수를 가집니다. $N, M \le 8$로 매우 작기 때문에 백트래킹으로 모든 경우를 출력해도 시간 내에 충분히 통과합니다.
• 복구의 중요성: 지난번 13023번(ABCDE) 문제와 마찬가지로, used[i] = false 처리를 잊는 순간 탐색 가능한 경로가 급격히 사라져 오답이 나옵니다. 백트래킹의 핵심은 언제나 '원상복구'입니다.