[BOJ] 6603번 로또 / 사용언어 : 파이썬(python)

※ 문제링크

6603번: 로또

해당 문제는 DFS와 백트래킹을 활용하여 푸는 문제였다. 주어진 숫자에 대해 알고리즘을 활용하여 조합수를 구하고 그 중 만족하는 수만 구하면 되는 문제라 어렵지않게 풀 수 있는 문제였다. 자세한 문제풀이 방법과 코드는 아래와 같다.

1. 입력받은 숫자를 리스트로 만들고, 첫번째 요소가 0이고, 리스트의 길이가 1이면 반복문을 중지하도록 조건을 건다.

2.  첫번째 숫자를 k로 그 뒤의 숫자는 n-list로 분할하여 저장한 후 dfs와 백트래킹을 수행할 함수를 작성한다.

3. 숫자들의 순서는 상관없는 조합문제이므로 시작 숫자를 정해 구현할 수 있게 조건을 건다. 

4. 조건을 만족하는 조합이 완성되면 출력하고, 초기화하여 반복적으로 명령을 수행하여 출력한다.

 

t = 0
while True:
    number_list = list(map(int, input().split()))
    if number_list[0] == 0 and len(number_list) == 1:
        break
    if t > 0:
        print('')
    k = number_list[0]
    n_list = number_list[1:]
    n_list.sort()
    arr = []
    check = [False] * k
    def dfs(start):
        if len(arr) == 6:
            print(*arr)
            return
        
        for i in range(start, k):
            if check[i]:
                continue
            
            arr.append(n_list[i])
            check[i] = True
            
            dfs(i)
            arr.pop()
            check[i] = False
    dfs(0)
    t += 1

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.