[김태원 알고리즘] 부분집합 구하기 (DFS)

사용 언어: Python3

문제

풀이

내 풀이

def DFS(v, lst):
    if v > N:
        return
    
    lst.append(v) # ✅ v를 포함 O
    DFS(v+1, lst)

    print(' '.join(map(str, lst)))

    lst.pop() # ✅ v를 포함 X
    DFS(v+1, lst)
    
N = int(input())
DFS(1, [])

• DFS()의 파라미터로 사용한 원소들을 넘겨준다.

다른 풀이

def DFS(v):
    if v == N + 1:
        for i in range(1, N+1):
            if ck[i] == 1: # 사용한 노드들 출력
                print(i, end=' ')
        print()
    else:
        ck[v] = 1 # v 노드를 사용 O
        DFS(v+1)

        ck[v] = 0
        DFS(v+1) # v 노드를 사용 X


N = int(input())
ck = [0] * (N+1) # 사용했는지 안했는지 체크 변수
DFS(1)

• ck 리스트를 이용해 사용한 원소를 표시해두었다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기