[Python-CodingTest] 6-10. 🌟 조합 구하기 (DFS: 깊이우선탐색)

조합 구하기

문제 정리

입력

4 2

처리 과정

1. DFS()의 인자로 src를 하나 더 주기
2. src는 for문의 시작지점으로, DFS를 재귀 호출할 때에 +1 해준다.

출력

1 2 
1 3 
1 4 
2 3 
2 4 
3 4 
6

내 답

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

def DFS(L,src): # src는 for문의 시작지점
    global cnt
    if src>m:
        for x in res:
            print(x,end=' ')
        print()
        cnt+=1
    else:
        for i in range(src,n+1):
            if ch[i]==0:
                res[L]=i
                ch[i]=1

                DFS(L+1,src+i)
                ch[i]=0
                


if __name__=="__main__":
    n,m=map(int,input().split())

    res=[0]*m
    ch=[0]*(n+1)
    cnt=0

    DFS(0,1) # 1부터 시작하니까 src에는 1
    print(cnt)

풀이

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

def DFS(L,src): # src는 for문의 시작지점
    global cnt
    if L==m:
        for x in res:
            print(x,end=' ')
        print()
        cnt+=1
    else:
        for i in range(src,n+1): # 🌟 i의 시작지점은 src
            res[L]=i
            DFS(L+1,i+1) # 🌟 src가 아니라 가지(=i)에 +1 주의!

if __name__=="__main__":
    n,m=map(int,input().split())

    res=[0]*m
    cnt=0

    DFS(0,1) # 1부터 시작하니까 src에는 1
    print(cnt)

정리

• 조합에는 체크리스트(=ch)가 필요없다.
• DFS()의 인자에 for문의 시작 지점인 src를 추가한다.

---

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

맨 위로 이동하기