섹션 8 DFS, BFS - 4. 중복순열 구하기

📌 문제 설명

1부터 N까지의 자연수가 적힌 구슬이 있을 때,
중복을 허용하여 M번을 뽑아 일렬로 나열하는 모든 경우를 출력하라.

• 같은 숫자를 여러 번 뽑을 수 있다 (중복 허용)
• 출력은 사전순으로 오름차순

---

📝 입력 & 출력

입력

• 첫 번째 줄: 자연수 N, M (3 ≤ N ≤ 10, 2 ≤ M ≤ N)

출력

• 가능한 중복순열을 한 줄에 하나씩 출력
• 출력 순서는 사전순

---

🔹 예제 입력 & 출력

예제 입력

 

3 2

예제 출력

 

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

---

💡 해결 방법

✅ 핵심 개념: 중복순열 (Permutation with Repetition)

• 중복 허용 → 뽑을 때마다 모든 숫자를 다시 선택 가능
• 깊이 L이 m에 도달할 때마다 출력
• DFS를 이용해 순서를 고려하며 선택

---

💻 코드 구현 (Java)

package partDfsBfs;

import java.util.*;

public class Problem4 {
	static int[] pm;
	static int n, m;

	public void DFS(int L) {
		if (L == m) {
			for (int x : pm) System.out.print(x + " ");
			System.out.println();
		} else {
			for (int i = 1; i <= n; i++) {
				pm[L] = i;
				DFS(L + 1);
			}
		}
	}

	public static void main(String[] args) {
		Problem4 T = new Problem4();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		pm = new int[m];
		T.DFS(0);
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 입력 처리 및 배열 초기화

n = kb.nextInt(); // 구슬의 범위
m = kb.nextInt(); // 뽑을 횟수
pm = new int[m];  // 현재 구성 중인 순열

---

2️⃣ DFS 재귀 함수

public void DFS(int L)

• L: 현재 깊이(몇 개를 뽑았는지)

---

3️⃣ 종료 조건

if (L == m) {
	for (int x : pm) System.out.print(x + " ");
	System.out.println();
}

• M개를 모두 뽑았으면 출력

---

4️⃣ 중복 허용 순열 탐색

for (int i = 1; i <= n; i++) {
	pm[L] = i;
	DFS(L + 1);
}

• 모든 숫자(1~N)를 다시 선택할 수 있음
• 따라서 중복이 허용된 순열이 생성됨

---

⏳ 시간 복잡도 분석

• 완전탐색 깊이: M
• 각 단계에서 선택 가능한 수: N
• 전체 경우의 수: O(N^M)
  (중복을 허용하므로 각 자리마다 N개의 선택 가능)

---

🧠 핵심 정리

• 이 문제는 중복을 허용한 순열 문제이며 DFS로 구현 가능
• 종료 조건은 깊이가 M에 도달했을 때
• 반복문 안에서 매번 pm[L] = i로 값을 채우고 다음 깊이로 진입
• 중복 제거가 필요한 순열/조합 문제와 혼동하지 않도록 주의

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런