[n6603] 로또 in python

---

백트래킹을 사용하여 풀어나간 문제!

이번에는 방문하는 노드 체크 과정을 빼먹지 않고 잘 했다!

for문에서 시작점 부분을 함수 매개변수로 넘겨주는 부분을

설정하지 않아서 애먹었던...

 

cnt가 6 => 즉, 6개의 숫자를 모두 뽑아낸 경우에는

그 숫자들을 모두 출력한다.

 

print(*array)를 하게 되면,

배열 형식으로 출력되지 않고

1 2 3 4 5 6 이런식으로 출력된다!

# k=array[0]
# array[1]~array[7] = 원소 배열

def dfs(array, cnt, temp, i):
    k = array[0]

    if cnt == 6:
        print(*temp)
        return

    for i in range(i, k + 1):
        if visited[i]:  # 방문한 노드
            continue
        visited[i] = 1
        temp.append(array[i])
        dfs(array, cnt + 1, temp, i)
        temp.pop()
        visited[i] = 0


while True:
    array = list(map(int, input().split()))
    visited = [0] * (array[0] + 1)
    if array[0] == 0:
        break
    dfs(array, 0, [], 1)
    print()

---

좀 더 효율적인 코드를 살펴보았다.

from itertools import combinations
import sys
input=sys.stdin.readline

while 1:
    arr = input().split()

    if arr.pop(0) == '0':
        break

    for i in combinations(arr, 6):
        print(" ".join(i))

    print()

combination 함수를 이용하여 손쉽게 값을 구할 수도 있다.

combinations(array,6) -> 6개의 숫자를 뽑아내는 것- > 조합

permutations(array,6) -> 순열