Algorithm - 부분집합 구하기(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[부분집합 구하기(DFS)]

 

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

 

 

*입력 설명

첫 번째 출에 자연수 N(1 ≤ N ≤ 10)이 주어진다.

 

*출력 설명

첫 번째 줄부터 각 줄에 하나씩 부분집합을 출력한다.

단, 공집합은 출력하지 않는다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_45.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 2 3 
1 2 
1 3 
1 
2 3 
2 
3 

'''

 

input_45.txt(입력)

3

 

 

중요내용

1. 변수 ch는 집합의 원소를 사용했는지, 사용하지 않았는지를 체크하기 위한 체크변수로 사용된다.
2. ch[v] = 1은 리스트의 인덱스 번호와 매칭되는 원소를 사용했음을 나타내는 코드이다.
3. ch[v] = 0은 리스트의 인덱스 번호와 매칭되는 원소를 사용하지 않았음을 나타내는 코드이다.
4. 나중에 리스트 ch에서 벨류 값이 1인 인덱스를 출력해주면 그 결과 값이 해당 집합의 모든 부분집합이 된다.
5. print()는 출력된 결과 값들 간의 줄바꿈을 시켜주는 코드이다.