[백준] 15649번: N과 M (1) - JAVA

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

[문제]

---

[해설]

1. 문제 이해

 

• 문제 요약:
  1부터 N까지 자연수 중에서 중복 없이 M개를 선택해 길이가 M인 수열을 모두 구하는 문제입니다.
  • 출력은 사전 순으로 증가하는 순서여야 합니다.
  • 중복되는 수열은 출력하면 안 됩니다.
• 입력:

N M

• 예) 3 1 → N=3, M=1
   
• 출력 예시:
  • 중복 없이 선택
  • 길이가 M인 수열

1
2
3

 

• 제약:

1 ≤ M ≤ N ≤ 8 

• N과 M이 작기 때문에 완전탐색(백트래킹) 가능

 

 

2. 핵심 아이디어

 

• 완전 탐색 + 백트래킹
  • 길이 M인 수열을 만들기 위해 재귀적으로 수를 선택
  • 이미 선택한 수는 제외 (visit 배열 사용)
• 재귀 함수 설계
  • 매 단계에서 선택할 수 있는 수를 순회
  • 선택하지 않은 수를 배열에 넣고, 재귀 호출 → 깊이(depth) +1
  • M개를 선택했으면 배열 출력
• 배열과 방문 체크 배열 사용
   

static int[] arr; // 현재 수열
static boolean[] visit; // 숫자 선택 여부

• 방문 체크 → 중복 방지
• 배열 → 출력할 수열 저장
   
• 출력 형식
  • Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(" "))
  • 공백으로 연결한 문자열 한 줄씩 출력

 

 

---

[코드]

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class BeakJoon_15649 {

    static int N;
    static int M;
    static int[] arr;
    static boolean[] visit;

    public static void backtrack(int depth) {
        if (depth == M) {
            // 출력
            System.out.println(Arrays.stream(arr)
                .mapToObj(String::valueOf)
                .collect(Collectors.joining(" ")));
            return;
        }

        for (int i = 0; i < N; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            arr[depth] = i + 1;

            backtrack(depth + 1);

            visit[i] = false;
            arr[depth] = 0;
        }
    }

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

        backtrack(0);
    }
}