[알고리즘/java] 인프런 자바 알고리즘 강의 : 부분집합 구하기(DFS)

[알고리즘/java] 인프런 자바 알고리즘 강의 : 부분집합 구하기(DFS)

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

문제 : 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하라. (공집합은 제외)

--N=3인 경우를 예로 진행.

{1, 2, 3}의 부분 집합을 구할 때는 각 원소를 사용하냐(O)/ 안 하냐(X)의 경우로

2 * 2* 2의 부분집합이 나온다.

여기서 우리가 구할 것은 공집합을 제외하기 때문에 다음과 같다.

1 2 3

1 2

1 3

1

2 3

2

3

>> 부분집합을 만드는 경우를 상태트리로 만들어 해당원소를 사용하느냐(O) / 안 하느냐(X)로 나눈다.

하나의 종료지점을 만나면 (L == N+1) 하나의 부분집합이 만들어지는 것이다.

<부분집합을 출력하는 코드>

public class Main { private static int n; private static int[] ch; public static 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) { // TODO Auto-generated method stub n = 3; ch = new int[n + 1]; DFS(1); } }

>> 각 원소를 사용하는지 안하는지를 체크하기 위해 int형 배열 ch를 이용한다.

앞서 말했듯이, 하나의 부분집합이 만들어지는 경우는 L==n+1인 경우이므로 공집합이 아닐 때

check배열 값이 1인 원소들을 출력한다.

from http://bumbleb22.tistory.com/8 by ccl(A) rewrite - 2021-12-11 18:28:02