자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 부분집합 구하기 (DFS)

 

https://hyejin.tistory.com/1257

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 이진 트리 순회

-> 이전 문제 풀이 

 

 

6. 부분집합 구하기 

설명

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요.

 

입력

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

 

출력

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.

단 공집합은 출력하지 않습니다.

 

예시 입력 1 

3

 

예시 출력 1

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

 

 

문제 풀이 1

public class FindingASubset
{
   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)
   {
      FindingASubset findingASubset = new FindingASubset();
      Scanner scanner = new Scanner(System.in);
      int L = scanner.nextInt();
      n = L;
      ch = new int[n + 1];
      findingASubset.DFS(1);
   }
}

👾 : DFS 관련 문제 나오면 어렵다.. 그래서 결국 이번에도 풀지 못하고... 강사님의 강의를 들었다. 

사실 이번에 DFS 에 대해서 처음 공부하기도 하니.. 강의 확실히 듣고, 나중에 관련 문제 나올 때 응용할 수 있도록 익혀둬야 겠다. 

 

문제는 우선 DFS(1) 에서 DFS(2), DFS(2) 를 호출해주는데 이때 왼쪽 DFS(2)는 해당 값을 부분집합에 포함한다는 뜻(ch[2] = 1) 이고, 오른쪽 DFS(2)는 해당 값을 부분 집합에서 포함하지 않는다는 뜻이다. (ch[2] = 0)

이런식으로 가지 치기를 해서 부분 집합을 구해줄 것이다. 

 

 

1️⃣

static int n; // 집합 원소의 개수
static int[] ch; // 부분집합으로 사용한다, 하지 않는다 체크하기 위해서

이번에는 전역 변수 n과 ch int형 배열을 선언했다. 

n은 집합 원소의 개수를 나타내고, ch는 n 만큼의 배열을 선언해서 해당 값을 포함할지 (1) 안할지(0) 를 지정해줄 것이다. 

 

2️⃣

public static void main(String[] args)
{
   FindingASubset findingASubset = new FindingASubset();
   Scanner scanner = new Scanner(System.in);
   int L = scanner.nextInt();
   n = L;
   ch = new int[n + 1];
   findingASubset.DFS(1);
}

다음에는 입력 값 L 을 받고, 위에서 선언한 전역변수 n에 L 값을 대입해주고, ch 배열의 크기는 n + 1로 선언해준다. 

n+1로 선언하는 이유는 ch[0]은 제외하고 할 예정이라서... 

그리고 DFS 함수를 호출하는데 맨 처음 1부터 대입해서 시작한다. 

 

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 {
      ch[L] = 1;
      DFS(L + 1); // 트리의 왼쪽 (사용한다)
      ch[L] = 0;
      DFS(L + 1); // 트리의 오른쪽 (사용하지 않는다.)
   }
}

 

DFS 함수에서는 L 값을 매개변수로 받는데 우선 1부터 시작한다. 

그럼 DFS(1) 인데 이때 if-else로 만약 L이 n+1 이되면 그땐 배열의 값 중 1인 인덱스 값을 출력해줄 것이다. 

L이 n+1이 아니라면 이제 ch[L]에 우선 1 값을 대입해주고, 그 다음 DFS(2) 를 호출한다. 

... 이런식으로 나아가다가 L이 n+1 즉, 여기선 4가 되면 ch 배열에서 1인 값의 인덱스를 출력해주고,  -> 1 2 3 출력 

다시 DFS(3) 으로 돌아온다. 

 

 

 

다시 DFS(3) 으로 돌아온다. DFS(3) 에서 ch[3] = 0으로 값을 설정해주고, 그 다음 DFS(4)를 호출한다. 

그러면 DFS(4)는 n+1 이므로, ch 배열의 값이 1인 인덱스를 출력한다. -> 1 2 출력 

다음 DFS(3) 이 끝났으니 DFS(2)로 돌아온다. 

 

 

DFS(2)로 돌아와서 ch[2] = 0 으로 변경해주고, DFS(3) 을 호출한다. 

그러면 또 반복해서 DFS(3) 은 ch[3] = 1 하고, DFS(4) 호출해서 ch가 1인 인덱스 값 호출한다. -> 1 3 호출 

그리고 다시 DFS(3)으로 돌아간다. 

 

 

그리고 다시 DFS(3)으로 돌아오면 이제 ch[3] = 0 을 대입하고, DFS(4)를 호출해서 다시 ch의 값이 1인 인덱스를 호출해준다. -> 1 출력 

 

... 이런식으로 반복하면 부분 집합을 출력할 수 있다. 

 

+ 추가로 더 해보자면... 

DFS(2) 도 그러면 끝났으므로 다시 DFS(1)로 돌아와서 ch[1] = 0 을 설정한 다음, DFS(2) 를 호출한다. 

그럼 DFS(2)는 다시 ch[2] =1 하고, DFS(3) 호출하고, ch[3] = 1 설정한 다음, DFS(4) 를 만나면 ch의 값이 1인 인덱스 값을 호출한다 . -> 2 3 출력 

그러고 다시 DFS(3) 으로 돌아오면 ch[3] = 0 이고 DFS(4) 를 호출해 ch 배열의 원소 값이 1인 인덱스 값을 호출한다. 

-> 2 출력 

그러면 DFS(3)도 끝났고, 다시 DFS(2)로 돌아와서 ch[2] = 0 으로 설정하고 다시 DFS(3)을 호출한다. 

그러면 DFS(3) 은 ch[3] = 1 하고, DFS(4) 호출하므로 ch 배열의 원소 값중에 1인 인덱스 값을 호출하면 -> 3 출력 

그 다음 DFS(3)으로 돌아오고, ch[3] = 0 을 설정한 다음, DFS(4) 호출하면 이제 모든 값이 000이므로 출력하는게 없이 끝나게 된다 !