6.3 부분 집합 구하기(DFS)

문제

부분집합 구하기(DFS)

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

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

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

▣ 입력예제 1
3

▣ 출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3

---

풀이

def DFS(v):
    if v==n+1:
        print(ch)
        print()
        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)

-ch의 의미

[0]*(n+1)--> [0,0,0...0] 0가 n+1개인 리스트가 생성됨

이는 1부터 n까지의 숫자에서 부분집합으로 포함 여부를 결정하는 리스트이다.

ch[i]==1인 경우 해당 값은 부분집합으로 포함되고

0인 경우는 부분 집합에 포함되지 않는다.

ch 예시

위 사진의 경우 집합은 1만 있는 것이다

 

-DFS에서 두 경우로 나눠지는 지점을 설정하기

else:
        ch[v]=1
        DFS(v+1)
        ch[v]=0
        DFS(v+1)

ch[v]가 1로 설정하는 경우와 0으로 설정하는 경우로 나누어서 분리한다.

이렇게 두 노드로 나누어야 경우의 수가 모두 표현된다

 

-DFS 나머지 코드

if v==n+1:    
        for i in range(1,n+1):
            if ch[i]==1:
                print(i, end=' ')
        print()

v가 n+1인 경우에는 함수를 마무리하고 출력해야 한다

따라서 앞서 언급한 ch가 1인 원소는 나란히 출력한다