파이썬 알고리즘-44 (DFS/BFS) 부분집합 구하기

44.부분집합 구하기(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:
        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)

반성점

• DFS/BFS 이론은 분명 공부했는데 적용이 전혀 안된다. 한심

배운 것

• 백트래킹: 모든 경우의 수를 고려하는 알고리즘으로, 모든 가능한 케이스가 나열된 상태공간트리를 작성해서 문제를 푼다. 백트래킹의 종류로 DFS/BFS가 있으며 모든 경우의 수를 구해야 할 때는 DFS, 최단거리를 구할 때는 BFS를 사용해서 문제를 푼다.