[Python-CodingTest] 6-3. 부분집합 구하기 (DFS: 깊이우선탐색)

부분집합 구하기

문제 정리

입력

3

처리 과정

1. 원소를 부분집합으로 사용할 때와 사용하지 않을 때의 상태로 나눠서 접근
2. 상태를 담을 체크 리스트(ch) <- 원소 번호와 ch의 인덱스가 동일
3. ch[i]==1이면 사용, ch[i]==0이면 사용하지 않음
4. 종착 지점에서 체크 리스트의 인덱스를 출력

출력

1 2 3
1 2
1 3
1
2 3
2
3

풀이

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

def DFS(v):
    if v==n+1: # 종착 지점
        for i in range(1,n+1):
            if ch[i]==1: # 사용(=1)하는 원소만 출력
                print(i, end=' ')
        print()
    else:
        ch[v]=1 # 원소를 부분집합으로 사용
        DFS(v+1)
        ch[v]=0 # 원소를 부분집합으로 사용X
        DFS(v+1)

if __name__=="__main__":
    n=int(input())
    ch=[0]*(n+1) # 원소를 부분집합으로 사용하는지, 사용하지 않는지 체크
    DFS(1)

정리

• 상태를 담을 리스트 추가
• 종착 지점에서 리스트의 값이 1인 인덱스만 출력

---

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

맨 위로 이동하기