[DFS기초] 부분 집합 구하기

부분 집합 구하기

 

 

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

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

▣ 출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.

 

▣ 입력예제 1

3

 

▣ 출력예제 1

1 2 3
1 2
1 3

1

23

2
3

 

 

나의 코드

def DFS(n,ch):
    if n==0:
       for i in range(1,len(ch)):
           if ch[i]==1:
               print(i,end=' ')
       print()
    else:
        ch[n]=1
        DFS(n-1,ch)
        ch[n]=0
        DFS(n-1,ch)


n=int(input())
ch=[0]*(n+1)
DFS(n,ch)

3까지의 부분 집합을 구하기 위해

DFS를 사용해서 3이 포함되냐 ? 안되냐 ? 로 둘로 나누어 가며 체크 배열을 사용했다.

 

 

 

정답 코드

import sys
sys.stdin=open("input.txt", "r")
def DFS(v):
    if v==n+1:
        for i in range(1, n+1):
            if ch[i]==1:
                print(i, end=' ')
        print()
    else:
        ch[v]=1
        DFS(v+1)
        ch[v]=0
        DFS(v+1)

if __name__=="__main__":
    n=int(input())
    ch=[0]*(n+1)
    DFS(1)

 

나의 코드와 접근법이 같지만 나는 3부터 시작해서 1까지 내려가고 정답코드는 1부터 시작해 3으로 가는 방향으로 탐색을 한다.