파이썬 알고리즘 044 | 부분집합 구하기(DFS) ***

44. 부분집합 구하기(DFS)

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램
을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
▣ 출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.
단 공집합은 출력하지 않습니다.
▣ 입력예제 1
3
▣ 출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3

<내 풀이>

• 우선 이전에 했던 자기 본연의 임무를 먼저 수행하고, 왼 & 오른쪽 출력해주는 애를 쓰면 일단 전체 범위일 때마다 자신의 역할이 한번씩은 나오는데, 나머지 애들은 대체 어떻게 처리를 해야지 일부분씩만 돌고 멈춰버릴 수 있는것인지 모르겠다
• 자기가 1, 2, 3을 향해 왔던 길을 모두 정리해주어야 하는 것 같은데 어떻게 접근해야할 지를 모르겠다

def DFS(x) :
    if 0<x<=n :
        print(x)
        DFS(x*2)
        DFS(x*2+1)

    else : 
        return        
if __name__=='__main__' :
    n=int(input())
    DFS(1)
    

<풀이>

• 원소를 사용한다, 안한다는 상태트리를 잘 구성하고 이러한 상태트리 의해 재귀만 잘 호출하면 된다
• 상태트리를 만들때 앞의 원소를 포함하기도 하고 안 포함하기도 하고
  
• 저런 식의 상태트리를 만들어서

def DFS(x) :
    if x==n+1: #만약에 입력값이 3이면 4가 종착역임, 종료지점에 오면 그때서야 출력해주면 됨
        for i in range(1,n+1) :
            if ch[i]==1 :
                print(i, end=' ')
        print()
        return
    else : 
        ch[x]=1 #사용한다는 것 (리스트에 1이라고 채워주기)
        DFS(x+1)
        ch[x]=0 #사용하지 않는 것 (리스트에 빵 넣어주기)
        DFS(x+1)
                
if __name__=='__main__' :
    n=int(input())
    ch=[0]*(n+1) # 원소를 포함시킬지 포함시키지 않을지 결정해주는 거
    DFS(1)

<반성점>

• DFS, 재귀함수를 잘 구현하지 못하겠다
• 복습이 필수로 요구되어야 한다

<배운 점>

• 상태트리를 구현하는 방법,