부분집합 구하기(DFS)

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

 

▣ 입력설명

첫 번째 줄에 자연수 N(1<=N<=10)

 

▣ 출력설명

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

단, 공집합은 출력하지 않음

 

▣ 입력예제

3

 

▣ 출력예제

1 2 3

1 2

1 3

1

2 3

2

3

---

내가 쓴 코드

import sys
sys.stdin = open("input.txt",'rt')

def DFS(num, subset):
    if num == N+1:
        if subset:
            for x in subset:
                print(x,end=' ')
            print()
    else:
        subset.append(num)
        DFS(num+1,subset)
        subset.pop(-1)
        DFS(num+1,subset)



if __name__ == '__main__':
    N = int(input())
    DFS(1,[])

 

상태 트리

내가그린 상태트리

 

모범답안

#모범답안
import sys
sys.stdin = open("input.txt",'rt')

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)

 

느낀점

1. DFS 재밌네..... 어렵다 근데..
흐름이 익숙하지 않아서 그런것같다
그러면 답은 뭐다? 많이 풀어보깅.

2. DFS 함수 정의 할때,
우선 if-else문으로 if: 결과를 뽑을 때(종료지점), else:탐색 
이런식으로 상황을 나누고
상황이 전개되는 흐름을 살펴보면서 알고리즘 설계를 하자!
아직은 익숙하지 않으니까
스택프레임을 그려서 함수 호출의 흐름을 직접 살펴보면서 코딩하면 
수월하게 할 수 있을듯

3. 상태트리를 그려보고 트리 DFS 재귀호출!
상태트리를 그리는게 중요하구낭..

 

---

다시 풀어보기

#다시 풀어보기
import sys
sys.stdin = open("input.txt")

def DFS(v):
    if v == N+1:
        for i in range(1,N+1):
            if include[i] == 1:
                print(i, end = ' ')
        print()
    else:
        include[v] = 1
        DFS(v+1)
        include[v] = 0
        DFS(v+1)

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