[백준] 6603 로또 - Python

6603번: 로또

POINT

Brute Force

• 모든 경우의 수를 탐색하여 정답을 찾는다.
• 즉, 전체 탐색을 사용한다. (순차 탐색, BFS, DFS 등)

Backtracking + DFS = Combinations

• 백트래킹과 DFS를 함께 사용하여 조합을 구현한다.

풀이1️⃣

조합 내장함수(combinations)를 사용한다.

from itertools import combinations

while True:
    data = list(map(int, input().split()))
    
    # 0이 입력되면 종료
    if data[0] == 0:
        break
        
    k, s = data[0], data[1:]
    
    cases = list(combinations(s, 6)) # s에서 6개의 숫자를 뽑는 모든 경우의 수
    for case in cases:
        for num in case:
            print(num, end=" ")
        print()
        
    print() # 한 줄 띄우기

풀이2️⃣

내장함수를 사용하지 않고, 백트래킹과 DFS으로 조합을 구현한다.

def dfs(start, cnt):
    # 6번 모두 뽑으면 출력
    if cnt == 6:
        for num in out:
            print(num, end=" ")
        print()
        
    for i in range(start, k):
        out.append(s[i])
        dfs(i + 1, cnt + 1) # 현재 추가한 숫자 다음부터 다시 함수 실행
        out.pop() # 한 케이스 출력 후 숫자 하나 제거 → i가 하나 증가하여 다음 숫자 append

while True:
    data = list(map(int, input().split()))
    
    # 0을 입력받으면 종료
    if data[0] == 0:
        break
        
    k, s = data[0], data[1:]
    out = [] # 로또 숫자 6개를 담을 배열
    dfs(0, 0)
    print()