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

승래·2026년 1월 28일

백준 백트래킹 자바

15649- N과 M(1)

문제 바로가기

1. 문제 요구사항

입력: 자연수 $N$ 과 $M$ 이 주어진다. ( $1 \le M \le N \le 8$ )
조건: 1부터 $N$ 까지 자연수 중에서 중복 없이 $M$ 개를 고른 수열을 모두 구해야 한다.
출력:
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
- 각 수열은 공백으로 구분해서 출력한다.

2. 접근 방식 (Algorithm)

이 문제는 순열(Permutation)을 구하는 문제로, 백트래킹을 사용하여 해결할 수 있다.

1) 핵심 로직: 재귀(DFS)와 방문 배열

arr 배열: 현재 탐색 중인 수열을 담을 공간. 크기는 $M$ .
visit 배열: 특정 숫자가 이미 수열에 포함되었는지 확인하는 용도. 크기는 $N+1$ .
depth 변수: 현재까지 몇 개의 숫자를 선택했는지 나타낸다. (재귀의 깊이)

2) 탐색 과정

DFS 함수 호출: depth가 0인 상태로 시작한다.
반복문 순회 ( $1 \sim N$ ): 1부터 $N$ 까지의 숫자를 하나씩 시도한다.
가지치기 (Pruning): 만약 visit[i]가 false라면 (아직 사용하지 않은 숫자라면):
- 해당 숫자를 방문 처리(visit[i] = true)한다.
- 결과 배열(arr[depth])에 숫자를 담는다.
- 다음 깊이로 재귀 호출(dfs(depth + 1))한다.
- [중요] 원상 복구 (Backtracking): 재귀가 끝나고 돌아오면, 다음 순서를 위해 방문 처리를 해제(visit[i] = false)한다.
기저 조건 (Base Case): depth == M이 되면 수열이 완성된 것이므로, 결과를 출력 버퍼에 담고 리턴한다.

3) 출력 최적화

반복 횟수가 많아질 경우 System.out.print를 매번 호출하면 시간 초과가 발생할 수 있다.
StringBuilder를 사용하여 출력할 문자열을 한 번에 모은 뒤, 마지막에 System.out.println으로 출력하여 성능을 높였다.

3. 소스 코드 (Java)

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[m];
        boolean[] visit = new boolean[n+1];

        dfs(n, m, 0, arr, visit);
        System.out.println(sb.toString());
    }

    static void dfs(int n, int m, int depth, int[] arr, boolean[] visit) {
        if(depth == m) {
            for(int num : arr) {
                sb.append(num + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i = 1; i <= n; i++) {
            if(!visit[i]) {
                arr[depth] = i;
                visit[i] = true;
                dfs(n, m, depth + 1, arr, visit);
                visit[i] = false;
            }
        }
    }
}