[BOJ] 6603. 로또(Python) / DFS

www.acmicpc.net/problem/6603

6603번: 로또

간단한 DFS로 조합(Combination)을 구현한 문제다.

# 소요시간 12분

• lottos에 담긴 숫자들 중 순서를 고려하지 않고 6개를 뽑아 차례로 출력한다.
• 이미 배열은 오름차순으로 되어있기 때문에 그대로 이미 뽑혔는지 확인해주며 뽑히지 않았다면 뽑은 표시 후 다음 자릿수에서 탐색한다.
• depth == 6이 될 때 출력한다.

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline

def comb(depth, pos):
    if depth == 6:
        print(*order)
        return
    for i in range(pos, k):
        order.append(lottos[i])
        comb(depth+1, i+1)
        order.pop()

while True:
    lottos = list(map(int, input().split()))
    k = lottos.pop(0)
    if not lottos:
        break
    order = []
    comb(0, 0)
    print()

---

• 시간 : 152ms / 메모리 : 124560KB
• 고찰 : combination 라이브러리로 금방 구할 수 있었지만 dfs로 직접 구현하면 조건을 추가하는 등 커스터마이징이 용이하다는 장점이 있다. 가볍게 풀기 좋은 문제였다!