[BOJ] 15657번: N과 M (8)

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

* 백트래킹: "경로를 탐색하다가 해가 될 가능성이 없으면 즉시 되돌아가 다른 경로를 탐색하는" 알고리즘

문제 정리

• N개의 자연수 중에서 M개를 고른 수열: N개의 주어진 숫자들 중에서 M개를 선택하여 수열을 만듭니다.
• 같은 수를 여러 번 골라도 된다: 중복 선택이 허용됩니다.
• 고른 수열은 비내림차순이어야 한다: A1​≤A2​≤⋯≤AM​ 와 같이, 뒤에 오는 숫자는 앞에 오는 숫자보다 작으면 안 됩니다.
• 수열은 사전 순으로 증가하는 순서로 출력: 최종 결과도 사전 순으로 정렬되어야 합니다. (이 조건은 입력으로 주어진 N개의 수를 미리 정렬하고, DFS 탐색 시 올바른 순서로 탐색하면 자동으로 만족됩니다.)

백트래킹의 적용 원리

백트래킹은 "경로를 탐색하다가 해가 될 가능성이 없으면 즉시 되돌아가 다른 경로를 탐색하는" 알고리즘입니다. 15657번 문제에서 백트래킹이 어떻게 적용되는지 단계별로 설명하겠습니다.

1. 초기 설정 및 정렬:
   • 주어진 N개의 자연수를 오름차순으로 정렬합니다. 이렇게 하면 나중에 수열을 구성할 때 "비내림차순" 조건을 쉽게 만족시킬 수 있고, "사전 순 출력" 조건도 자동으로 만족됩니다.
   • 수열을 저장할 result 또는 sequence와 같은 배열(또는 리스트)을 준비합니다.
2. DFS 함수 정의:
   • DFS 함수는 일반적으로 현재까지 선택한 숫자의 개수(count 또는 depth)와 다음 숫자를 선택할 시작 인덱스(start_index 또는 idx)를 매개변수로 가집니다.
   • 종료 조건 (Base Case): 만약 현재까지 선택한 숫자의 개수가 M과 같아지면 (즉, 길이가 M인 수열이 완성되면), 해당 수열을 출력하고 함수를 종료합니다. 이것이 하나의 유효한 해를 찾았을 때의 처리입니다.
3. 재귀 호출 (탐색):
   • DFS 함수 내에서 for 루프를 사용하여 다음 숫자를 선택합니다.
   • 핵심 백트래킹 조건: 비내림차순 유지: for 루프의 시작점을 start_index로 설정합니다. 즉, 현재 수열에 마지막으로 추가된 숫자(또는 이전에 탐색을 시작했던 인덱스)부터 다시 탐색을 시작합니다.
     • for i = start_index 부터 N-1까지 반복합니다.
     • 현재 i번째 숫자를 수열에 추가합니다.
     • 재귀 호출: dfs(count + 1, i) 와 같이 재귀적으로 호출합니다.
       • 여기서 i를 다음 호출의 start_index로 넘겨주는 것이 중요합니다. 왜냐하면 다음 숫자는 현재 선택한 숫자와 같거나 커야 하기 때문입니다. 만약 start_index를 0으로 넘겨주면 내림차순 수열도 만들어질 수 있습니다.
     • 백트래킹 (되돌리기): 재귀 호출이 끝난 후에는 현재 수열에 추가했던 숫자를 다시 제거합니다. (파이썬의 경우 pop() 사용, C++이나 Java의 경우 배열을 사용한다면 명시적으로 제거할 필요는 없지만, 다음 탐색을 위해 스택에서 해당 원소를 제외하는 개념으로 이해하면 됩니다.) 이는 다음 숫자를 선택하기 위해 "가지치기"를 한 후 원래 상태로 돌아와서 다른 경로를 탐색할 수 있도록 준비하는 과정입니다.

예시를 통한 이해 (N=3, M=2, 주어진 숫자: 1, 7, 9)

1. 초기 호출: dfs(0, 0) (현재까지 0개 선택, 0번 인덱스부터 시작)
2. dfs(0, 0):
   • i = 0 (숫자 1 선택): result = [1]
     • dfs(1, 0) 호출
     • dfs(1, 0):
       • i = 0 (숫자 1 선택): result = [1, 1]
         • dfs(2, 0) 호출
         • dfs(2, 0): count == M 이므로 [1, 1] 출력. return
       • result = [1] (백트래킹: 1 제거)
       • i = 1 (숫자 7 선택): result = [1, 7]
         • dfs(2, 1) 호출
         • dfs(2, 1): count == M 이므로 [1, 7] 출력. return
       • result = [1] (백트래킹: 7 제거)
       • i = 2 (숫자 9 선택): result = [1, 9]
         • dfs(2, 2) 호출
         • dfs(2, 2): count == M 이므로 [1, 9] 출력. return
       • result = [1] (백트래킹: 9 제거)
     • result = [] (백트래킹: 1 제거)
   • i = 1 (숫자 7 선택): result = [7]
     • dfs(1, 1) 호출
     • dfs(1, 1):
       • i = 1 (숫자 7 선택): result = [7, 7]
         • dfs(2, 1) 호출
         • dfs(2, 1): count == M 이므로 [7, 7] 출력. return
       • result = [7] (백트래킹: 7 제거)
       • i = 2 (숫자 9 선택): result = [7, 9]
         • dfs(2, 2) 호출
         • dfs(2, 2): count == M 이므로 [7, 9] 출력. return
       • result = [7] (백트래킹: 9 제거)
     • result = [] (백트래킹: 7 제거)
   • i = 2 (숫자 9 선택): result = [9]
     • dfs(1, 2) 호출
     • dfs(1, 2):
       • i = 2 (숫자 9 선택): result = [9, 9]
         • dfs(2, 2) 호출
         • dfs(2, 2): count == M 이므로 [9, 9] 출력. return
       • result = [9] (백트래킹: 9 제거)
     • result = [] (백트래킹: 9 제거)

이 과정을 통해 [1, 1], [1, 7], [1, 9], [7, 7], [7, 9], [9, 9]와 같이 비내림차순이면서 중복을 허용하는 모든 길이가 M인 수열을 사전 순으로 얻을 수 있습니다. 백트래킹은 유효하지 않은 경로(여기서는 비내림차순을 어기는 경우)를 미리 차단하고, 한 경로의 탐색이 끝나면 그 경로에서 추가했던 요소를 다시 제거하여 다른 경로를 탐색할 수 있도록 돕는 역할을 합니다.

---

 

• 초기 설정 및 정렬:
  • static int[] arr;: 주어진 N개의 자연수를 저장하는 배열입니다.
  • Arrays.sort(arr);: 가장 중요합니다. 입력으로 받은 숫자들을 오름차순으로 정렬합니다. 이는 두 가지 핵심 조건(비내림차순과 사전 순 출력)을 자동으로 만족시키는 데 결정적인 역할을 합니다.
  • static int[] result;: M개의 숫자를 고른 수열을 저장하는 배열입니다.
• dfs(int depth, int start) 함수:
  • depth: 현재까지 result 배열에 채워진 숫자의 개수를 나타냅니다. (0부터 M-1까지)
  • start: 다음에 arr 배열에서 숫자를 선택할 때, 어디서부터 탐색을 시작할지 결정하는 인덱스입니다.
• 종료 조건 (Base Case):
  • if (depth == M): result 배열에 M개의 숫자가 모두 채워졌을 때 (즉, 길이가 M인 수열이 완성되었을 때), 해당 수열을 StringBuilder에 추가하고 return합니다. 이 부분이 하나의 유효한 "해(solution)"를 찾았을 때의 처리입니다.
• 재귀 호출 (탐색 및 가지치기):
  • for (int i = start; i < N; i++):
    • i = start로 시작하는 것이 핵심적인 백트래킹 및 비내림차순 유지 전략입니다.
      • 이전에 result[depth-1]에 arr[start-1] (또는 그 이전)의 값을 넣었다면, 이번에는 arr[start]부터 시작하여 이전 값보다 크거나 같은 값만 선택하게 됩니다. 예를 들어 arr = [1, 7, 9]이고 이전에 1을 선택했다면, 다음 숫자는 1, 7, 9 중에서만 선택할 수 있습니다. 1보다 작은 숫자를 선택할 필요가 없으므로 효율적인 탐색이 가능합니다.
      • 이는 중복 허용 (같은 수를 여러 번 골라도 된다) 하면서 비내림차순 (고른 수열은 비내림차순이어야 한다) 조건을 만족시키는 방식입니다.
  • result[depth] = arr[i];: 현재 i번째 arr의 숫자를 result 배열의 depth 위치에 저장합니다. (수열에 숫자를 추가하는 행위)
  • dfs(depth + 1, i);: 다음 숫자를 고르기 위해 재귀 호출을 합니다.
    • depth + 1: result 배열의 다음 칸을 채우기 위해 depth를 1 증가시킵니다.
    • i: 이것이 중요합니다. 다음 재귀 호출에서 숫자를 탐색할 시작 인덱스를 현재 선택한 arr[i]의 인덱스 i로 넘겨줍니다. 이렇게 함으로써 이전에 선택한 숫자(arr[i])보다 크거나 같은 숫자만 다음으로 선택하게 되어 "비내림차순" 조건을 만족시킵니다. 만약 여기에 0을 넘겨주면 중복은 허용하지만 비내림차순은 보장되지 않습니다.
  • 명시적인 "되돌리기(백트래킹)" 동작은 필요 없음: Java의 경우 result 배열은 static으로 선언되어 있지만, result[depth] = arr[i]로 값을 할당한 후 재귀 호출 dfs(depth+1, i)이 끝나고 돌아오면, 현재 depth에서 다른 i 값으로 result[depth]를 다시 덮어쓰거나, 혹은 depth가 줄어들면서 이전 depth에 해당하는 result의 값이 사용되지 않게 되므로 명시적으로 result[depth]를 비우거나 초기화할 필요가 없습니다. 이는 배열의 인덱스를 활용한 백트래킹의 자연스러운 특징입니다. (물론 ArrayList를 사용한다면 remove()를 해주어야 합니다.)

 

import java.util.*;
public class Main {
    static int N, M;
    static int[] arr;
    static int[] result;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr); // 정렬

        result = new int[M];
        System.out.println("==== 백트래킹 시작 ====");
        dfs(0, 0);
        System.out.println("==== 백트래킹 종료 ====");
        System.out.println(sb);
    }

    static void dfs(int depth, int start) {
        System.out.println("현재 depth: " + depth + ", start: " + start + ", path: " + Arrays.toString(result));

        if (depth == M) {
            sb.append(Arrays.toString(result)).append("\n");
            return;
        }

        for (int i = start; i < N; i++) {
            result[depth] = arr[i];
            System.out.println("-> arr[" + i + "]=" + arr[i] + " 선택 (depth=" + depth + ")");
            dfs(depth + 1, i);
            System.out.println("<- arr[" + i + "]=" + arr[i] + " 제거 (depth=" + depth + ")");
        }
    }
}

정렬

• 입력받은 숫자들을 오름차순으로 정렬 → 비내림차순 수열을 자동으로 생성 가능

dfs (재귀 호출)

• depth: 현재 뽑은 수열의 길이
• start: 다음 숫자를 선택할 인덱스 (중복 허용 & 비내림차순 위해 i부터 시작!)
• depth == M이면, result를 출력

출력 최적화

• StringBuilder를 사용해 출력 속도 향상
• System.out.println(sb);로 한꺼번에 출력

---