문제
1부터 N까지의 자연수 중에서 M개를 선택하는 문제다. N과 M (1), (2)와 달리 같은 수를 여러 번 골라도 된다. 즉, 중복 순열(중복 허용 순열)을 구하는 문제다.
입력
- 첫째 줄: N, M (1 ≤ M ≤ N ≤ 7)
출력
가능한 모든 수열을 사전 순으로 출력 (한 줄에 하나씩)
예제
| 입력 | 출력 |
|---|---|
3 1 | 1 2 3 |
3 2 | 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 |
풀이
방문 배열 없이 DFS로 중복 순열을 생성한다. 중복을 허용하므로 매 깊이마다 1~N을 전부 탐색하면 된다.
dfs(depth)함수에서depth가 M에 도달하면 현재 배열을 출력한다.- 1~N까지 순회하며 현재 깊이에 숫자를 저장하고
dfs(depth + 1)을 호출한다. - 방문 배열이 없으므로 같은 수를 여러 번 선택할 수 있다.
- 시작 인덱스도 전달하지 않으므로 항상 1부터 탐색하여 순서가 다른 수열도 모두 출력된다.
핵심 아이디어: N과 M 시리즈를 비교하면, (1)은 방문 배열로 중복 없는 순열, (2)는 시작 인덱스로 중복 없는 조합, (3)은 방문 배열과 시작 인덱스 모두 없어 중복 허용 순열이다. 코드 변경이 최소화된다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day43BOJ15651N과M3DFS연습 { // 15651 N과 M(3) DFS
static int[] arr;
static int N, M;
static StringBuilder sb;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
sb = new StringBuilder();
N = sc.nextInt();
M = sc.nextInt();
arr = new int[M];
dfs(0);
System.out.println(sb);
sc.close();
}
static void dfs(int depth) {
if (depth == M) {
for (int n : arr) {
sb.append(n).append(" ");
}
sb.append("\n");
return;
} // 1 ~ N포함 까지
for (int i = 1; i <= N; i++) {
arr[depth] = i;
dfs(depth + 1);
}
}
}복잡도
- 시간: O(N^M) — 매 깊이마다 N가지 선택, M번 반복
- 공간: O(M) — 재귀 호출 스택 깊이와 결과 배열