[파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 부분집합 구하기 (DFS)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

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

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(v):
    # 종료지점
    if v == (N+1):
        for i in range(1, N+1):
            if checked[i] == 1:
                print(i, end='')
        print()
    else:
        checked[v] = 1 # 부분집합으로 사용하겠다.
        DFS(v+1)
        
        checked[v] = 0 # 부분집합으로 사용하지 않겠다.
        DFS(v+1)

N = int(input())
checked = [0] * (N+1) # 방문 여부 체크
DFS(1)

그림으로 이해해보자.

 

- DFS에서 상태트리를 많이 사용한다고 한다. 위의 문제에 대한 상태트리를 그림으로 표현해보았다.

- 부분집합으로 사용하고, 안하고의 유무를 나타내기 위한 도구로 visited 라는 리스트를 사용한다. (사용O → 1 / 사용X → 0)

- 만약 N이 3이라면 (N+1)인 4가 종료지점이 되고, 종료지점에서는 visited 리스트의 원소 중 1인 것들만 출력한다.