[15652번] N과 M (4)

문제: https://www.acmicpc.net/problem/15652

 

 

이 문제는 백트래킹 문제이다. 먼저 백트래킹이 뭔지 알아보자

1. 백트래킹(Backtracking)이란?

백트래킹은 가능한 모든 경우의 수를 탐색하되, 조건에 맞지 않으면 즉시 되돌아가는(Back) 알고리즘이다.

• 탐색: 일반적으로 재귀 함수(DFS)를 사용하여 깊이 들어간다.
• 가지치기(Pruning): 조건에 맞지 않는 길은 더 이상 가지 않고 끊어버리는 것이다. 이것이 단순한 완전 탐색(Brute Force)과 백트래킹의 차이다.

 

2. 문제 분석 

 

이 문제의 조건은 두 가지 핵심 포인트가 있다.

1. 중복 허용: 같은 수를 여러 번 골라도 된다. (예: 1 1, 2 2)
2. 비내림차순: 수열이 뒤로 갈수록 같거나 커져야 한다. (예: 1 2는 되지만 2 1은 안 됨)

 

3. 풀이 아이디어: '상태 공간 트리' 그리기

 

이 문제를 트리 구조로 시각화해서 생각해보자. N=3,M=2라고 가정해 보자. (1부터 3까지 숫자 중 2개를 고름)

1. 첫 번째 숫자 고르기: 1, 2, 3 중 하나를 고른다.
2. 두 번째 숫자 고르기:
   • 첫 번째로 1을 골랐다면? -> 다음 숫자는 1, 2, 3 모두 가능 (1 이상이어야 하므로)
   • 첫 번째로 2를 골랐다면? -> 다음 숫자는 2, 3만 가능 (2 이상이어야 하므로)
   • 첫 번째로 3을 골랐다면? -> 다음 숫자는 3만 가능 (3 이상이어야 하므로)

이 과정에서 가장 중요한 것은 현재 내가 몇 번째 깊이(Depth)에 있는지와 이전에 고른 숫자가 무엇인지(혹은 어디서부터 탐색을 시작할지)를 함수에게 알려주는 것이다.

 

4. 핵심 로직 설계

 

재귀 함수를 만들 때 두 가지 변수(파라미터)가 필요하다.

1. depth (깊이): 현재 숫자를 몇 개 골랐는지 카운트한다. depth == M이 되면 수열이 완성된 것이므로 출력하고 함수를 종료(return)한다.
2. start (시작 인덱스): 비내림차순 조건을 만족하기 위해 필요하다. 지금 고를 숫자는 start 이상이어야 한다는 기준점이다.

 

5. 논리 흐름

• 함수 dfs(depth, start)를 호출한다.
• 반복문을 i = start 부터 N 까지 돌린다. (중요: 1부터가 아니라 start부터이다.)
• 배열에 숫자 i를 담는다.
• 다음 재귀 호출을 한다: dfs(depth + 1, i)
  • 여기서 두 번째 인자가 i + 1이 아니라 i인 이유는 중복을 허용하기 때문이다. (현재 고른 i를 다음에도 또 고를 수 있음)

 

6. 최종 코드

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

public class Main {
    public static int N, M;
    public static int[] arr; // 수열을 담을 배열
    public static StringBuilder sb = 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];

        // 깊이 0, 시작 숫자 1부터 탐색 시작
        dfs(0, 1);

        System.out.println(sb);
    }

    // depth: 현재까지 고른 숫자의 개수
    // start: 이번에 고를 숫자의 시작 범위 (비내림차순 유지용)
    public static void dfs(int depth, int start) {
        // [Base Case] 목표 깊이(M)에 도달하면 출력 저장 후 리턴
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }

        // [Recursive Step] start부터 N까지 반복
        for (int i = start; i <= N; i++) {
            arr[depth] = i; // 현재 깊이에 i를 저장

            // 다음 깊이로 이동
            // 중복 허용이므로 다음 단계의 start도 i 그대로 유지 (i부터 다시 고를 수 있음)
            dfs(depth + 1, i);
        }
    }
}