섹션 7 Recursive, Tree, Graph - 6. 부분집합 구하기(DFS)

📌 문제 설명

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성한다.
단, 공집합은 출력하지 않는다.

예를 들어, N=3이면 집합 {1,2,3}의 부분집합을 출력하는 것이다.

---

📝 입력 & 출력

입력

• 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 10)

출력

• 각 줄마다 하나의 부분집합을 출력한다.
• 원소들은 오름차순으로 나열하고, 공집합은 출력하지 않는다.

---

🔹 예제 입력 & 출력

예제 입력

3

 

예제 출력

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

---

💡 해결 방법

이 문제는 모든 부분집합(Subset) 을 구하는 문제이다.

DFS(깊이우선탐색)를 이용하여 다음과 같이 문제를 해결할 수 있다:

• 각 원소를 "부분집합에 포함시킬지 말지" 결정한다.
• 즉, 트리 구조로 보면 한 노드마다 "선택함" 또는 "선택 안 함" 두 가지 경우가 발생한다.
• N개의 원소에 대해 각각 두 가지 선택을 하므로 전체 경우의 수는 2^N 가지가 된다.
• 이때, 선택된 원소들을 모아 출력하고, 선택된 게 하나도 없으면 (공집합) 출력하지 않는다.

DFS 재귀 호출 구조

• 왼쪽: 현재 원소를 부분집합에 포함시키는 경우
• 오른쪽: 현재 원소를 부분집합에 포함시키지 않는 경우

---

💻 코드 구현 (Java)

전체 코드

package partRecursiveTreeGraph;

public class Problem6 {
	static int n;
	static int[] ch;

	public void DFS(int L) {
		if (L == n+1) {
			String tmp = "";
			for (int i = 1; i <= n; i++) {
				if (ch[i] == 1) tmp += (i + " ");
			}
			if (tmp.length() > 0) System.out.println(tmp);
		} else {
			ch[L] = 1; // 현재 숫자를 부분집합에 포함
			DFS(L+1);  // 다음 숫자로 이동
			ch[L] = 0; // 현재 숫자를 부분집합에 포함하지 않음
			DFS(L+1);  // 다음 숫자로 이동
		}
	}

	public static void main(String[] args) {
		Problem6 T = new Problem6();
		n = 3;
		ch = new int[n+1];
		T.DFS(1);
	}
}

---

📖 코드 설명

1️⃣ 부분집합 표시용 배열 사용

static int[] ch;

 

• ch[i] == 1이면 i번째 원소를 부분집합에 포함시킨다.
• 포함 여부를 기록하는 체크용 배열이다.

 

2️⃣ DFS 재귀 호출

public void DFS(int L) {
	if (L == n+1) {
		...
	} else {
		ch[L] = 1; // 현재 숫자를 부분집합에 포함
		DFS(L+1);  // 다음 숫자로 이동
		ch[L] = 0; // 현재 숫자를 부분집합에 포함하지 않음
		DFS(L+1);  // 다음 숫자로 이동
	}
}

• 매개변수 L은 현재 검사할 원소의 번호를 의미한다.
• L == n+1이 되면 모든 원소에 대해 포함 여부 결정을 완료한 상태이므로 결과를 출력한다.
• 그렇지 않다면
  • ch[L]=1 → 현재 원소를 부분집합에 포함시키고 다음 레벨로 재귀 호출
  • ch[L]=0 → 현재 원소를 포함시키지 않고 다음 레벨로 재귀 호출

3️⃣ 종료 조건 (부분집합 출력)

public void DFS(int L) {
	if (L == n+1) {
		String tmp = "";
		for (int i = 1; i <= n; i++) {
			if (ch[i] == 1) tmp += (i + " ");
		}
		if (tmp.length() > 0) System.out.println(tmp);
	} else {
		...
	}
}

• tmp 문자열에 포함된 원소만 이어붙여 출력한다.
• 만약 선택된 원소가 하나도 없다면 출력하지 않는다. (공집합 제외)

---

⏳ 시간 복잡도 분석

 

• 숫자 하나마다 포함/비포함 2가지 경우 → 경우의 수 2^N
• 각 경우마다 선택된 원소를 모아 출력 → O(N)
• 최종 시간 복잡도: O(N × 2^N)

주의:
N이 최대 10이므로 2^10 = 1024로 manageable(처리 가능한) 크기다.
(N이 20 이상이면 다른 최적화 기법이 필요할 수 있다.)

---

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

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

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