섹션 8 DFS, BFS - 6. 순열 구하기

📌 문제 설명

10 이하의 N개의 자연수가 주어졌을 때 이 중 M개를 선택하여 일렬로 나열하는 모든 순열을 출력하라.

• 중복 없이 선택해야 하며
• 순서를 고려하여 나열해야 한다.
• 출력은 사전순(오름차순) 으로 정렬되어야 한다.

---

📝 입력 & 출력

입력

• 첫 줄: 자연수 N, M (3 ≤ N ≤ 10, 2 ≤ M ≤ N)
• 둘째 줄: N개의 자연수 (오름차순)

출력

• 가능한 모든 순열을 한 줄에 하나씩 출력
• 출력 순서는 사전순으로 오름차순

---

🔹 예제 입력 & 출력

예제 입력

 

3 2  
3 6 9

예제 출력

 

3 6  
3 9  
6 3  
6 9  
9 3  
9 6

---

💡 해결 방법

✅ 핵심 전략: DFS + 방문 체크 배열

• DFS를 통해 깊이 L까지 탐색
• 현재 선택한 수를 pm[L]에 저장
• 중복 방지를 위해 ch[i] 배열로 방문 여부 체크
• 순열 생성이 끝나면 출력

---

💻 코드 구현 (Java)

package partDfsBfs;

import java.util.*;

public class Problem6 {
	static int[] pm, ch, arr;
	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 = 0; i < n; i++) {
				if (ch[i] == 0) {
					pm[L] = arr[i];
					ch[i] = 1;
					DFS(L + 1);
					ch[i] = 0; // 백트래킹
				}
			}
		}
	}

	public static void main(String[] args) {
		Problem6 T = new Problem6();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		arr = new int[n];
		ch = new int[n];
		pm = new int[m];
		for (int i = 0; i < n; i++) arr[i] = kb.nextInt();
		T.DFS(0);
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 입력 및 초기화

arr = new int[n];   // 입력 숫자 배열
ch = new int[n];    // 방문 체크 배열
pm = new int[m];    // 결과를 저장할 순열 배열

---

2️⃣ DFS 함수 구조

 

DFS(L + 1);         // 다음 깊이로 진입
ch[i] = 0;          // 백트래킹: 방문 해제

• 방문하지 않은 수만 선택 (ch[i] == 0)
• 하나 선택 후 다음 깊이로 이동
• 돌아와서 방문 해제 (백트래킹)

---

3️⃣ 종료 조건

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

• 깊이 m에 도달했을 때 현재 순열을 출력

---

⏳ 시간 복잡도 분석

• 총 경우의 수: P(N, M) = N! / (N - M)!
• 각 경로는 O(M)
• 전체 탐색은 O(N! / (N - M)!) 수준 → N ≤ 10이라 완전탐색 가능

---

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

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

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