백준 6603번. 로또 (Python / 파이썬)

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.
로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.
예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.
각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

---

문제 풀이

로또 문제는 49가지 수 중 k개의 수를 골라 집합 S를 만든 다음

집합 S에서 6개의 수를 고르는 경우의 수를 구하는 문제입니다.

 

Back Tracking 방법을 이용하면 수의 조합을 모두 구할 수 있습니다.

먼저 어떤 원소가 선택되었는지 체크할 list array를 만들어주었습니다.

array의 크기는 k이며 0으로 모두 초기화 된 상태입니다.

 

그 후 dfs 함수를 실행합니다. 6개의 수를 고를 때는

중복이 있으면 안되며, 오름차순이어야 합니다. 

따라서 현재 index보다 큰 index에 대해서만 수행되도록

start 변수를 이용해 현재 index 부터 반복문을 수행해줍니다.

 

반복문에서는 i번째 index의 array 값을 1로 만들어줍니다.

이 코드의 의미는 집합 S에서 i번째 원소가 선택되었다는 의미입니다.

그 다음 재귀함수를 수행하는데, 다음 index 값을 넘겨줍니다.

또한, 6개의 수가 선택됐음을 알리기 위해 count 변수를 이용하여

수가 하나씩 선택될 때마다 1증가시켜줍니다.

 

만약 count가 6이 되면 6개가 선택되었다는 뜻이므로

만약 array의 i번째 index 값이 1이라면 S의 i번째 index 값을 출력해줍니다.

그런다음 호출됐던 위치로 반환됩니다.

 

호출됐던 위치로 돌아가면 선택되었던 i번째 index 값을 1에서 다시 0으로 만들어줍니다.

이 과정을 입력이 될때마다 반복하도록 해주었고

만약 0이 입력되면 종료되도록 해주었습니다.

---

My Code

def dfs(start, count):
    if count == 6: # 만약 6개의 수가 선택되었다면
        for i in range(k):
            if array[i]: # array의 i번째 값이 1이라면 (선택된 수)
                print(s[i], end = ' ') # S의 i번째 값을 출력
        print()
        return # 호출됐던 위치로 반환

    for i in range(start, k): # 기준 index부터 반복문 수행
        array[i] = 1 # i번째 index 값 1로 만들어줌 (수를 선택)
        dfs(i + 1, count + 1) # 그 다음 index와 count+1을 넘겨주어 재귀함수 수행
        array[i] = 0 # 다시 i번째 index 값을 0으로 만들어줌


while True:
    data = list(map(int,input().split())) # 정수를 입력받아 list로 생성
    if data[0] == 0: # 만약 0이 입력되면 종료
        break
    k = data[0] # 입력된 list의 첫번째 값은 k (집합 S의 원소 수)
    s = data[1:] # 입력된 list의 나머지 값은 집합 S

    array = [0 for _ in range(k)] # 수가 선택되었는지 체크할 list
    dfs(0, 0) 

    print()