문제
1부터 N까지의 자연수 중에서 M개를 선택하는 문제다. 중복 없이 선택하고, 선택한 수열은 오름차순이 아닌 임의의 순서로 나열한다. 즉, 같은 수를 두 번 이상 고를 수 없으며 순서가 다른 수열은 서로 다른 수열로 취급한다. 이때 가능한 모든 수열을 사전 순으로 출력한다.
입력
- 첫째 줄: N, M (1 ≤ M ≤ N ≤ 8)
출력
가능한 모든 수열을 사전 순으로 출력 (한 줄에 하나씩)
예제
| 입력 | 출력 |
|---|---|
3 1 | 1 2 3 |
4 2 | 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 |
풀이
DFS(백트래킹)를 이용하여 중복 없는 순열을 생성한다. 방문 배열로 이미 선택한 숫자를 추적하며, 선택 후 재귀 호출하고 돌아오면 선택을 취소(backtrack)한다.
- 길이 M의 결과 배열
arr과 방문 배열visit을 선언한다. - 깊이
depth가 M에 도달하면 현재 배열을 출력하고 반환한다. - 1~N까지 순회하며 방문하지 않은 숫자를 선택하고
depth + 1로 재귀 호출한다. - 재귀에서 돌아오면 방문 표시를 해제하여 다른 경우를 탐색한다.
핵심 아이디어: 방문 배열 visit[i]로 중복 선택을 방지하고, 재귀 호출 전후로 visit[i] = true / false를 토글하는 전형적인 백트래킹 패턴이다. 순서가 중요한 순열이므로 모든 위치에서 1~N을 다시 탐색한다.
코드
package com.ssafy.an.day049;
import java.util.Arrays;
import java.util.Scanner;
public class Day38BOJ15649N과Mdfs풀이법 { // 15649 N과 M dfs 1단계
static int[] arr;
static boolean[] visit;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
arr = new int[M];
visit = new boolean[N];
dfs(N, M, 0);
sc.close();
}
private static void dfs(int N, int M, int depth) {
if (depth == M) {
System.out.println(Arrays.toString(arr).replaceAll("[\\[\\],]", ""));
return;
}
for (int i = 0; i < N; i++) {
if (!visit[i]) {
visit[i] = true;
arr[depth] = i + 1;
dfs(N, M, depth + 1);
visit[i] = false;
} // 재귀로 푸는 법 구선생님 도움..
}
}
}복잡도
- 시간: O(N! / (N-M)!) — N개 중 M개를 순서 있게 선택하는 순열 수
- 공간: O(M) — 재귀 호출 스택 깊이와 결과 배열